求运算次数 - 百度面试题
stone54321277
如果n为偶数，将其处以2；
如果n为奇数，可以加1或减1；
一直处理下去。
求最小运算次数。
发布于 1 年 之前 #
jeff lee
Member
int min(int n)
while(n!=1)
{
if (n%2==0) n=n/2;
else if (n+1/2%2==0) n++;
else n--;
count++;
}
count 是主函数定义的变量 计算循环次数即运算次数
不知道对不对 请不吝赐教
-------计算机初学者
发布于 1 年 之前 #
daydream9
Member
相当于用最少的2的幂把n拆成这些幂加减的形式吧，感觉贪心好像就是对的
发布于 1 年 之前 #
wahaha
Member
int min_cal_cnt(int n)
{
int count;
for(count=0; n>1; count++)
n&1 ? n++ : n>>=1; //n除以2可简化为位移.
return count;
}
or
int min_cal_cnt(int n)
{
int count;
for(count=0; n>1; count++)
n&1 ? n-- : n>>=1;
return count;
}
一个奇数加1或减1肯定回变成偶数,但n+1/2%2的运算优先级比较混乱,是不是少括号了.....
发布于 11 月 之前 #
hillwhite
Member
连位移都不需要
把整数数表示成二进制，直接取它的长度位数就OK了，比如11 表示成二进制是 1011， 那么把它算到1，只需要4次运算
发布于 9 月 之前 #
pugwoo
Member
@wahaha 当n=15时，只需要5次，而你的程序需要6次。
@hillwhite 当n=8时，1000，只需要3次，而非4次。
这道题用广搜可以做出来，数学上的公式我还导不出，广搜可以做到时间O(N)空间O(N)，用HASH表记录搜索过的值。
发布于 2 星期 之前 #
pugwoo
Member
今天吃晚饭的时候，突然想起这道题，原来就是素数筛选法阿。。
2、4、8、16。。。的次数是2^i的i
3可以由2和4的最小者加1，然后6、12、24、48、...全部都知道了
接着5由4和6最小者加1得出。。继续筛选。。
这样线性时间+线性空间就可以搞定N以内所有的运算次数