首页 > 试题广场 >

对一个正整数作如下操作:如果是偶数则除以 2,如果是奇数则加

[单选题]

对一个正整数作如下操作:如果是偶数则除以 2,如果是奇数则加 1,如此进行直到 1 时操作停止,求经过 9 次操作变为 1 的数有多少个?

```
18
```
```
34
```
```
64
```
```
78
```

推荐

流

//34

#include <stdio.h>
int count=0;
void deal(int n,int cnt)
{
    if(cnt==9){
        count++;
        //printf("%d\n",n);
        return;
    }
    if(n%2) 
        deal(2*n,cnt+1);
    else{
        deal(2*n,cnt+1);
        if(n>2) 
            deal(n-1,cnt+1);
    }        
}
int main(void)
{
    deal(1,0);
    printf("%d\n",count);
}

编辑于 2015-01-28 14:56:41 回复(7)

shanhua

这题倒推可以找到规律的，和一楼的深搜一个意思

发表于 2015-03-22 17:08:38 回复(15)

牛客791082号

斐波那契数列。88个

发表于 2015-07-06 11:47:30 回复(0)

zhaojm09

最后2次操作一定是4->2->1。可以考虑前7次操作中，+1出现的次数。由于+1必然接除以2，因此可以出现的次数为0,1,2,3,4.

0次为全除以2,有1种；

1次有C₇ ¹=7种；

2次的话不能相邻出现，相当于5次除以2插缝2次加1，有C₆ ²=15种；

3次同上，有C₅ ³=10种；

4次只有1种；

因此共有1+7+15+10+1=34种

发表于 2015-04-07 16:59:27 回复(6)

牛客352205号

答案：34
奇数x逆推是2x ，偶数逆推是x-1和2x
因此这是一个斐波那契数列：
1，1，2，3，5，8，13，21，34

发表于 2015-07-28 17:05:09 回复(0)

indere

最后一次，也就是第九次为1，可以推出第八次只有一种可能：2
第八次为偶数2，偶数可以由（偶数/2）得来，也可以由（奇数+1）得来，由于题目说到1终止，所以第七次也只有一种可能：4
第六次：两种可能：8和3
由于偶数可以由偶数（偶数/2）和奇数（奇数+1）得来，奇数只能由偶数（偶数/2）得来，所以第五次有三种可能：2偶1奇
第四次：偶数可以得到偶数和奇数，奇数只能得到偶数：3偶2奇
同理第三次：5偶3奇
第二次：8偶5奇
第一次：13偶8奇
第零次：21偶13奇 ——总共21+13=34总可能值。

发表于 2016-06-11 11:28:13 回复(0)

张佃鹏

这个其实就是一个斐波那契数列而已：

因为1->2->4,前两步是固定的，那么对于4而言有如下情况：

4->3->6

4->8

也就是如果是奇数到上一个节点只有一种情况，如果是偶数到上一个节点那么就会两种情况

所以我们设当前偶数节点到起始节点还有n步，共有f（n）种走法，

（1）那么因为偶数节点到奇数节点的走法相当于偶数节点到奇数节点下一个节点的走法也就是f（n-2）；

（2）偶数节点到偶数节点的走法有f（n-1）种

也就是f（n）=f(n-1)+f(n-2)

其中f（1）=2；f（0）=1

最后求出f（7）=34（因为前两种走法是固定的）

发表于 2015-10-04 11:14:49 回复(0)

CloudCastle

如果逆推此题，可以知道 1 一定是由 2 ， 4 变化来的（因为2不能由1得到，不纳入以下讨论）
4 之后有可能是 8 和 3，因此分支开始。
每个偶数 2n 一定能产生两个分支——由4n 除以2得到，或者2n-1得到，
每个奇数 2n-1 只能是由偶数 4n-2除以2得到，
因此每个偶数逆推一次产生一个奇数和一个偶数，每个奇数逆推一次产生一个偶数
用一个很简单的函数循环7次就可以了（从4开始算），代码如下：
void func(int& numEven, int& numOdd)
{
    int e = numEven;
    int o = numOdd;
    numEven = e + o;
    numOdd = e;
}

int main()
{
    int a = 1;
    int b = 0;
    for ( int i = 0; i < 7; ++i )
    {
        func(a, b);
    }
    cout << a << " " << b;
    return 0;
}
得到偶数21个，奇数13个，总数34个。

发表于 2015-08-09 16:08:50 回复(0)

zzoecode

#include <iostream>
using namespace std;

int fun(int n, int cur)
{
	if (n == 1)
		return 1;
	if ((cur & 0x1) == 1)
		return fun(n - 1, cur * 2);
	else
		return fun(n - 1, cur * 2) + fun(n - 1, cur + 1);
}
void main(void)
{
	cout << fun(9, 1) << endl;
}

发表于 2015-09-03 23:47:44 回复(1)

nurnoch

这道题可以采用从后（即1开始）往前推的策略。

一个奇数加1，必定变成一个偶数；而一个偶数除以2可能是奇数也可能是偶数。

1 -> 2 -> 4->[8,3]->....

最终可以列出每次变换，对应的个数。

1次变换：1个数；

2次变换：1个数

3次变换：2个数；

4次变换：3个数；

5次变换：5个数；

......

可以看出来是一个斐波那契数列，所以得到9次变换为44.

发表于 2015-08-28 22:34:29 回复(0)

小菜鸡工程师

我怎么算出来55个...

发表于 2021-09-08 14:59:13 回复(0)

vivi_sea

通过1次操作变为1的数为2，再经过一次操作变为2的数为4、1，即通过两次操作变为1的数为4、1，
再经过1次操作变为4的数有两个为3、8、2，即通过3次操作变为1的数有两个为3，8，…，
经过1、2、3、4、5…次操作变为1的数依次为1、2、3、5、8…，这即为斐波拉契数列，
后面的数依次为：13+8=21，21+13=34，34+21=55．
即经过9次操作变为1的数有55个．

发表于 2015-03-26 17:34:53 回复(0)

Evidence

分析：

得到偶数的前一步操作，可能是奇数，也可能是偶数

得到奇数的前一步操作，只能是偶数

9次操作得到1

等效于 8次操作得到2

等效于 7次操作得到4（因为不能得到1）

等效于 6次操作得到3、8

等效于 5次操作得到6、7、16

等效于 4次操作得到偶数3个，奇数2个，共5个

等效于 3次操作得到偶数5个，奇数3个，共8个

等效于 2次操作得到偶数8非，奇数5个，共13个

等效于 1次操作得到偶数13个，奇数8个，共21个

等效于原始偶数21个，奇数13个，共34个

发表于 2018-07-19 13:23:10 回复(0)

钜子墨苍离

从1开始倒推导回去，正整数n为奇数时翻倍，偶数时-1或者翻倍。总结内在规律。当整数为奇数时只有翻倍一种选择，为偶数时有翻倍和-1两种选择。假设倒推到第k步时，可能性为m个奇数，n个偶数，那么第k+1步时，n个奇数，m+n个偶数，第k+2步时，n+m个奇数，m+2n个偶数.

（m+n）+（n+m+n）=（n+m+m+2n），斐波那契数列。

发表于 2015-08-30 01:18:10 回复(0)

氷_临

答案是错的，应该是1+1+2+3+5+8+13+21+34=88

发表于 2024-03-20 16:06:14 回复(0)

牛客476014889号

已练

发表于 2022-09-08 05:56:56 回复(0)

可以签但没必要

//34 
#include <stdio.h>
#define N 1000
void main()
{      int i,n=0,x,j;      for(j=2;j<10000;j++)      {         
      i=j;         
      x=0;         
      while(x<=9)         
      {                      
      if(i%2==1)                 
      i=i+1;             
      else                 
            i=i/2;             
      x++;                 
      if (x==9&&i==1){n++;break;}             
      if (i==1)break;         
      }      }          printf("%d\n",n); }

编辑于 2019-07-11 15:57:04 回复(0)

二咩

定义O为偶数个数，G为奇数个数，则有：

第n-1项（O_n-1+G_n-1）_，第n项（O_n+G_n），第n+1项（O_n+1+G_n+1）

由于奇数+1操作与偶数除以2会有重复，重复个数即操作后的偶数个数，且偶数除以2可以覆盖到前一项所有数值个数，所以：

G_n+1=O_n=O_n-1+G_n-1

O_n+1=O_n+G_n

两等式相加 (O_n+1+G_n+1) = (O_n+G_n) + (O_n-1+G_n-1)

所以有 F(n+1)=F(n)+F(n-1)

编辑于 2019-04-25 14:06:13 回复(0)

大胖柚子

这是智力题？😂

发表于 2018-09-01 11:40:18 回复(0)

魔女和飞鱼

倒推下一步的偶数个数等于上一步的奇数和偶数个数和奇数等于上一步的偶数个数

编辑于 2018-08-04 14:58:16 回复(0)

aijialin

我看到这题首先想到的就是那个最大的数必定就是512 因为512 = 2^9，所以只需要遍历1~512之间的整数即可。

int main() {
    int count = 0;
    for ( int i = 1; i <= 512; i++ ) {
        int num = i;
        for ( int j = 0; j < 9; j++ ) {
            if ( (num & 0x01) == 0 ) num >>= 1; //num为偶数则除2
            else num += 1; 
            if ( j < 8 && num == 1 ) { break; } // 排除还没到9次就已经为1的数
            else if ( j == 8 && num == 1 ) { cout << i << " "; count++; }
        }
    }
    cout << endl << count << endl;
    return 0;
}

发表于 2018-03-17 15:55:19 回复(0)

提交观点

问题信息

数学运算

来自：腾讯2014校招研发工...

上传者：小海豹

难度：

45条回答 1173收藏 20084浏览

对一个正整数作如下操作:如果是偶数则除以 2,如果是奇数则加

问题信息

热门推荐

相关试题