1、實現一個函數，對一個正整數n，算得到1需要的最少操作次數。操作規則為：如果n為偶數，將其除以2;如果n為奇數，可以加1或減1;一直處理下去。

例子：

func(7) = 4，可以證明最少需要4次運算

n = 7

n-1 6

n/2 3

n-1 2

n/2 1

要求：實現函數(實現盡可能高效) int func(unsign int n);n為輸入，返回最小的運算次數。給出思路(文字描述)，完成代碼，并分析你算法的時間復雜度。

答：

[cpp] view plaincopyint func(unsigned int n)

{

if(n == 1)

return 0;

if(n % 2 == 0)

return 1 + func(n/2);

int x = func(n + 1);

int y = func(n - 1);

if(x > y)

return y+1;

else

return x+1;

}

假設n表示成二進制有x bit，可以看出計算復雜度為O(2^x)，也就是O(n)。

將n轉換到二進制空間來看(比如7為111，6為110)：

- 如果最后一位是0，則對應于偶數，直接進行除2操作。

- 如果最后一位是1，情況則有些復雜。

如果最后幾位是???01，則有可能為???001，???1111101。在第一種情況下，顯然應該-1;在第二種情況下-1和+1最終需要的步數相同。所以在???01的情況下，應該選擇-1操作。

如果最后幾位是???011，則有可能為???0011，???11111011。在第一種情況下，+1和-1最終需要的步數相同;在第二種情況下+1步數更少些。所以在???011的情況下，應該選擇+1操作。

如果最后有更多的連續1，也應該選擇+1操作。

如果最后剩下的各位都是1，則有11時應該選擇-1;111時+1和-1相同;1111時應選擇+1;大于四個1時也應該選擇+1;

[cpp] view plaincopyint func(unsigned int n)

{

if(n == 1)

return 0;

if(n % 2 == 0)

return 1 + func(n/2);

if(n == 3)

return 2;

if(n&2)

return 1 + func(n+1);

else

return 1 + func(n-1);

}

2、找到滿足條件的數組

給定函數d(n)=n+n的各位之和，n為正整數，如d(78)=78+7+8=93。這樣這個函數可以看成一個生成器，如93可以看成由78生成。

定義數A：數A找不到一個數B可以由d(B)=A，即A不能由其他數生成。現在要寫程序，找出1至10000里的所有符合數A定義的數。

回答：

申請一個長度為10000的bool數組，每個元素代表對應的值是否可以有其它數生成。開始時將數組中的值都初始化為false。

由于大于10000的數的生成數必定大于10000，所以我們只需遍歷1到10000中的數，計算生成數，并將bool數組中對應的值設置為true，表示這個數可以有其它數生成。

最后bool數組中值為false的位置對應的整數就是不能由其它數生成的。