1、一个K位的数N (K<=2000,N<=10^20)
找出一个比N大且最接近的数，这个数的每位之和与N相同
用代码实现之
例 3919999700
从右向左找到第一个非0 7,7– ,并且把6移到最后
继续扫碰到9就移到最后,找到第一个非9 1, 1++
最后变成 3920069999
2、题目：
实现函数int func(unsigned n)，其中n为正整数，返回从1到n（包含1和n）之间出现的1的个数，如func(13)=6，func(9)=1。（注意：不能将整数转化为字符串）
分析：
对于数n，可以把它分成三段，高位段most，当前位cur，低位段least，每一段分别为一个整数。对于一个有digit位的数，假设当前 位是左数第i位，则设一个临时变量tmp为10的digit-i次方，即比least多一位的最小整数。如数123456，为6位数，digit=6，设 当前为左起第3位，则i=3，most=12，cur=3，least=456，tmp=1000。
如果当前位大于1，则从1到n间出现在当前位出现的1的个数是most*tmp+tmp；如果等于1，则是most*tmp+least+1；如果小于，则为most*tmp。
int func(unsigned n)
{
int count = 0;
int digit = (int)log10(n) + 1;
int most, cur, least, tmp;
int i;
for (i=0; i<digit; ++i)
{
tmp = (int)pow(10, digit-i-1);
most = n / tmp / 10;
cur = (n / tmp) % 10;
least = n % tmp;
count += most * tmp;
if (cur > 1)
{
count += tmp;
}
else if (cur == 1)
{
count += least + 1;
}
}
return count;
}
题目：
实现一个函数，对于正整数n，算出得到1需要的最少操作次数：
如果n是偶数，将其除以2；如果n是奇数，可以加1或减1；一直处理下去，直到得到1。
示例：
ret=func(7);
ret=4，可以证明最少需要4次操作。
n=7;
n-1=6;
n/2=3;
n-1=2;
n/2=1;
要求：
实现函数（实现尽可能高效）int func(unsigned int n)；n是输入，返回最小的操作次数。给出思路（文字描述）并完成代码，然后分析算法的时间复杂度。
分析：
从数的二进制表示来看，偶数的最后一位为0，而奇数为1。如4d＝100b，而3d＝11b。除2操作与二进制的右移一位操作等价，故对偶数来说，右移一位即可；而奇数则需加1（或减1）。
在 最好的情况下，数n的最低位为1，其它位均为0,如10000b，这样的数右移log2n位即可变为1，这样消去除最高位外的其它位的平均代价为1。接着 考虑最低位为1的情况，由于不清楚是需加1还是减1，我们来看次低位（倒数第2位）。如果次低位为1，如11011b，则若加1一共需3次能消去后两位， 平均每位代价为1.5；若减1，则共需四次才能消去后两位，平均每位代价为2，故选择加1。如果次低位为0，则直接减1，消去后两位的代价为3，平均每位 代价为1.5。任何二进制数均可分段为若干个2位和0或1个1位组成，因此消去每位的最高代价为1.5，消去所有位的代价为1.5log2n；如果考虑到 后两位消去时向前面的进位，则消去所有位的代价最多为1.5log2n+1。综上，算法的时间复杂度为O(log2n)。
对于数3d＝11b，其若加1后需3次才能变为1，而减1可以后需2次。故对3d特殊考虑。
int func(unsigned int n)
{
int count = 0;
while (n != 1)
{
if ((n & 0×1) == 0)
{
n >>= 1;
}
else if ((n & 0×2) == 0)
{
--n;
}
else if (n != 3)
{
++n;
}
else
{
--n;
}
++count;
}
return count;
}
只用一次加法，求三个双字节数只和：
本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请
点击举报。
