计算最少操作次数。。。-白红宇

计算最少操作次数。。。

阅读量：2437 次

发布时间：2019-05-10

本文共 1160 字，大约阅读时间需要 3 分钟。

实现一个函数，对一个正整数n,算得到1需要的最少操作次数：

如果n为偶数，将其处以2;　　如果n为奇数，可以加1或减1;　　一直处理下去。

例子：

ret = func(7);

ret = 4,可以证明最少需要4次运算

n = 7

n—1 6

n/2 3

n-1 2

n/2 1

要求：实现函数(实现尽可能高效)

Int func(unsign int n);n为输入，返回最小的运算次数。

给出思路(文字描述)，完成代码，并分析你算法的时间复杂度。

#include <cstdlib>#include <iostream>using namespace std;int get1Count(unsigned int val){ int count = 0; for(int i=0; i<31; i++) { if(val & 1 == 1) count++; val >>= 1; if(val == 0) break; } return count;}int func(unsigned int value){ int count = 0; while(value != 1) { if(value % 2 == 0) { count++; value >>= 1; } else { int count1 = get1Count(value + 1); int count2 = get1Count(value - 1); if(count1 < count2) value++; else value--; count++; } } return count;}int main(int argc, char *argv[]){ unsigned int value; while(cin >> value) cout << func(value) << endl; system("PAUSE"); return EXIT_SUCCESS;}

对于一个奇数来说，是加1还是减1，关键是看+1 or -1后二进制中1的个数的多少，采用结果中1的个数较少的一个...

转载地址：http://kckqb.baihongyu.com/

你可能感兴趣的文章