迭代算法-验证谷角猜想

时间：2010-07-22 来源：chengxiaopeng

在网上看到这么一道关于迭代算法的练习题：验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象：对于任意一个自然数 n ，若 n 为偶数，则将其除以2; 若 n 为奇数，则将其乘以 3 ，然后再加 1 。如此经过有限次运算后，总可以得到自然数 1。人们把谷角静夫的这一发现叫做“谷角猜想”。要求：编写一个程序，由键盘输入一个自然数 n ，把 n 经过有限次运算后，最终变成自然数 1 的全过程打印出来。在这道题中，我们其中的有一个判断点，即：这个数是否是偶数，判断经过计算后值是否等于1，如果不等于1，则继续进行循环，因此我们大概可以猜得到，这个程序，一定是使用循环，判断的标准即，计算后的结果是否为1，在程序中应该还有一个函数，判断计算的数是否是偶数。经过这个的思路分析，程序基本上已经写出来了，代码如下：

#include <stdio.h>

int is_oushou(int); //判断一个数是否是偶数

int main(int argc,int *argv[])
{
    int i,j;
    printf("please input a numer[number > 0]:");
    scanf("%d",&i);

    do
    {
      j = i;
      if (is_oushou(j))
      {
         i = j / 2;
         printf("%d / 2 = %d\n",j,i);
      }
      else
      {
          i = j *3 +1;
          printf("%d * 3 + 1 = %d\n",j,i);
      }
    }while(i != 1);

    system("pause");
    return 0;
}

int is_oushou(int number)
{
    int result = 0;
    if (number > 0)
    {
       if(number % 2 == 0)
       {
                 result = 1;
       }
    }

    return result;
}

这道题练习题，网上也给出了源代码：

#include<stdlib.h>

                  int main()
                  {
                      int n;

                      puts("input n: ");
                      scanf("%d", &n);

                      puts("过程:");
                      printf("%d -> ", n);

                      while (n != 1)
                      {
                          if (0 == (n&1))
                              n = n / 2; //迭代关系式

                          else
                              n = n * 3 + 1; //迭代关系式

                          printf("%d -> ", n);
                      }
                      printf("\b\b\b\b \n");//去掉多余的“ -> ”

                      system("pause");
                      return 0;
                  }

代码更简洁，更紧凑，我喜欢这种风格，其中在if判断中，提供的源代码使用的是if (0 ==(n &1)) 其实这句话的意思是，让这个数与1进行按位于运算，我们知道如果是偶数，将其转化为二进制的时候，我们会发现此数的最后一位0，而奇数则最后一位是1，所以和1进行按位与运算，则偶数为0，奇数为1。呵呵。