和之前的Manager借来的一本书。
看了第一章，的确很不错。
让我开始深思自己和身边的人们，一举一动背后的原因。
第一章：相对性的真相
总结来说，就是关于人们爱比较的心态。
而因为这爱比较的心态而导致了不理性的行为。
引用里边的例子，一年份的报刊订阅费用：
电子版：59美元
印刷版：125美元
印刷版+电子版：125美元
根据实验证明，大部分的人们都会选择“印刷版+电子版”。。
因为相较之下，“印刷版+电子版”比起印刷版更值得。
比较的心态，让人们剔除了印刷版的选择，但是却突出了“印刷版+电子版”更为优势。
虽然电子版更为便宜，但是由于“印刷版+电子版”看起来更为优势，大部分都选择了“印刷版+电子版”。
另外一个发生过在我身边的例子。
还记得当初公司打算推出新的福利，所有员工都可以购买平板电脑。（前提条件，自己先掏腰包，公司后来以每个月退回的方式付给你。）
同事们兴致勃勃地去看了ipad的价钱，也看了ipad casing的价钱。
大部分都认同正版ipad casing的价钱太贵了，不是很值得（一个大约要一百到数百元）。
当新的福利正式落成，同事们开始购买ipad。。
有部分嫌正版ipad casing太贵的，结果都买了casing。
其实不难发现，一个ipad要两千多元，相较之下，casing反而更“便宜”了。
这和卖车子的同一个道理，买了数十千元的车子，不妨添多一两千元换个真皮座位。
若是要单独购买一两千元的真皮座位，相信也不多人会去购买了。
因为和车子相较之下，那一两千元反而变得便宜了。
当我身边的友人正犹豫是否要购买某物品时，我都会使用这招。
例子：A友人告诉我犹豫是否购买X, 我会告诉他/她，你都已经花了大笔钱买了Y，不妨再加那么一点钱买X（相较Y的价格，X显得便宜多)，去衬托/保护Y，不然就什么什么的。。
对于抑制力不坚定的人，屡试不爽。
Wednesday, April 9, 2014
Sunday, March 30, 2014
Update : 100 - The 3n + 1 problem
I was trying to optimize my 3n + 1 solution. My previous solution was through Brute Force method, which will calculate and max cycle length for every pairs of input. This solution was slow with the run time of 0.392s. The solution is in C++ as below:
Initially i was trying to use an array of int.. but seems like its too big and when i try to run it with eclipse, the program stopped working. :-(
Googling around and found out there are people out there using array of short int for the same question and its works.
The solution is in C as below:
#include<iostream>
using namespace std;
int main() {
unsigned int lower, upper, temp, m, n;
unsigned int i;
int counter = 1;
int max = 0;
while (cin >> lower >> upper) {
if (lower > upper) {
upper = m;
lower = n;
} else {
upper = n;
lower = m;
}
if (upper < 1000000 && lower > 0) {
for (i = lower; i <= upper; i++) {
temp = i;
while (i != 1) {
if (i & 1) {
i = (3 * i) + 1;
i = i >> 1;
counter += 2;
} else {
i = i >> 1;
counter++;
}
}
if (counter > max)
max = counter;
counter = 1;
i = temp;
}
cout << m << " " << n << " " << max << endl;
max = 1;
}
}
return 0;
}
So i changed to another implementation, which is calculate the max cycle length and saved it into a array.Initially i was trying to use an array of int.. but seems like its too big and when i try to run it with eclipse, the program stopped working. :-(
Googling around and found out there are people out there using array of short int for the same question and its works.
The solution is in C as below:
#include<stdio.h>
#define MAX 1000001
static unsigned short int cycle[MAX];
short int cycleLength(unsigned long int number) {
if (number < MAX) {
if (cycle[number]) {
return cycle[number];
}
if (number & 1) {
cycle[number] = 2 + cycleLength(((3 * number) + 1) >> 1);
} else {
cycle[number] = 1 + cycleLength(number >> 1);
}
return cycle[number];
}
if (number & 1) {
return 2 + cycleLength(((3 * number) + 1) >> 1);
} else {
return 1 + cycleLength(number >> 1);
}
}
int main() {
unsigned int first, second;
int counter;
unsigned short int maxCycle = 0;
unsigned short int temp;
cycle[1] = 1;
while (scanf("%u %u", &first, &second) != EOF) {
maxCycle = 0;
if (first < second) {
for (counter = first; counter <= second; counter++) {
temp = cycleLength(counter);
if (temp > maxCycle) {
maxCycle = temp;
}
}
} else {
for (counter = second; counter <= first; counter++) {
temp = cycleLength(counter);
if (temp > maxCycle) {
maxCycle = temp;
}
}
}
printf("%u %u %d\n", first, second, maxCycle);
}
return 0;
}
The run time after the optimization was 0.032s . Please feel free to comment if you found that the code or algorithm can be further optimize.
Wednesday, October 10, 2012
Euclid's Algorithm
I was trying around with some algorithm in order for me to get familiar with it.
First started with Euclid's Algorithm.
Loop
First test case with GCD for 252 and 105 (repeated 10 million times to record the time)
Second test case with GCD for 163231 and 152057 (repeated 10 million times to record the time)
Conclusion that i get is recursion way is faster than looping. The coding in recursion also much simpler.
Perhaps there are better way to code both method and this is open to discussion.
I believe there are still many room for me to improve.
First started with Euclid's Algorithm.
Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers, also known as the greatest common factor (GCF) or highest common factor (HCF). (quoted from Wikipedia)I tried with 2 method to implement it in a function, first with looping and second with recursion.
Loop
int loopGCD(int big, int small){Recursion
int temp;
while(small!=0){
temp = big%small;
big=small;
small=temp;
}
return big;
}
int recursionGCD(int big,int small){i tested around that both method for 5 times and record down the time used to process.
if(small==0){
return big;
}
return recursionGCD(small,big%small);
}
First test case with GCD for 252 and 105 (repeated 10 million times to record the time)
| No | loop | recursion |
| 1 | 0.484 | 0.447 |
| 2 | 0.484 | 0.475 |
| 3 | 0.48 | 0.457 |
| 4 | 0.488 | 0.458 |
| 5 | 0.494 | 0.452 |
| Average | 0.486 | 0.4578 |
Second test case with GCD for 163231 and 152057 (repeated 10 million times to record the time)
| No | loop | recursion |
| 1 | 1.249 | 1.051 |
| 2 | 1.233 | 1.246 |
| 3 | 1.227 | 1.048 |
| 4 | 1.222 | 1.02 |
| 5 | 1.292 | 1.041 |
| Average | 1.2446 | 1.0812 |
Conclusion that i get is recursion way is faster than looping. The coding in recursion also much simpler.
Perhaps there are better way to code both method and this is open to discussion.
I believe there are still many room for me to improve.
Saturday, January 15, 2011
11470 - Square Sums
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2465
Recursion method is used to solve this problem.
First of all, get the size of the grid. Even and odd number of the size will have some slightly different in the coding part especially the inner square.
Taking odd grid as example given in the question:
| 5 | 3 | 2 | 7 | 9 |
| 1 | 7 | 4 | 2 | 4 |
| 5 | 3 | 2 | 4 | 6 |
| 1 | 3 | 4 | 5 | 1 |
| 1 | 4 | 5 | 6 | 3 |
First of all, get the sum of outer most square.
5 + 3 + 2 + 7 + 9 + 1 + 4 + 5 + 6 + 1 + 1 + 1 + 4 + 5 + 6 + 3 = 63
In order to get the sum of this square, I get the sum for each row and column separately in the square.
| 5 | 3 | 2 | 7 | 9 |
| 1 | 7 | 4 | 2 | 4 |
| 5 | 3 | 2 | 4 | 6 |
| 1 | 3 | 4 | 5 | 1 |
| 1 | 4 | 5 | 6 | 3 |
5 + 3 + 2 + 7 + 9 = 26
| 5 | 3 | 2 | 7 | 9 |
| 1 | 7 | 4 | 2 | 4 |
| 5 | 3 | 2 | 4 | 6 |
| 1 | 3 | 4 | 5 | 1 |
| 1 | 4 | 5 | 6 | 3 |
5 + 1 + 5 + 1 + 1 =13
| 5 | 3 | 2 | 7 | 9 |
| 1 | 7 | 4 | 2 | 4 |
| 5 | 3 | 2 | 4 | 6 |
| 1 | 3 | 4 | 5 | 1 |
| 1 | 4 | 5 | 6 | 3 |
9 + 4 + 6 + 1 + 3 = 23
| 5 | 3 | 2 | 7 | 9 |
| 1 | 7 | 4 | 2 | 4 |
| 5 | 3 | 2 | 4 | 6 |
| 1 | 3 | 4 | 5 | 1 |
| 1 | 4 | 5 | 6 | 3 |
1 + 4 + 5 + 6 + 3 = 19
After that, sum up each row and column in square.
26 + 13 + 23 + 19 = 81
It stills not the correct answer yet, because we have to subtract out the intersection for in each row and column.
| 5 | 3 | 2 | 7 | 9 |
| 1 | 7 | 4 | 2 | 4 |
| 5 | 3 | 2 | 4 | 6 |
| 1 | 3 | 4 | 5 | 1 |
| 1 | 4 | 5 | 6 | 3 |
81 – ( 5 + 1 + 9 + 3 ) = 63
Now we got the sum of the outer most square and output it. We proceed to the 2nd outer most square where we reduced it to a smaller grid.
| 7 | 4 | 2 |
| 3 | 2 | 4 |
| 3 | 4 | 5 |
Same method as above is used, get the sum of each row and columns, then subtract out the intersection. The grid keep reduce and same steps keep repeat until we reach the most inner square. The most inner square is our base case in this recursion.
There are 2 type of the most inner square:
- Odd grid will only has 1 number in the most inner square
- Even grid will has 4 numbers in the most inner square as below :
| 2 | 4 |
| 4 | 5 |
Get the sum of the most inner square (for even) or output the only number (for odd) in the base case of the recursion.
P/S : Recursion is not the only method that able to solve this problem, using the loop will able to solve the problems as well.
Subscribe to:
Posts (Atom)