【23xiu.com-爱上秀-教育信息门户网】
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的位置对应的整数就是不能由其它数生成的。