爱因斯坦的阶梯问题

    爱因斯坦曾经提出过这样一道有趣的数学题：有一个长阶梯，若每步上2阶，最后剩下1阶；若每步上3阶，最后剩2阶；若每步上5阶，最后剩下4阶；若每步上6阶，最后剩5阶；只有每步上7阶，最后刚好一阶也不剩。请问该阶梯至少有多少阶。

    我们假设阶梯共有n阶，我们可以很快的列出下面的式子：

n mod 2 = 1

n mod 3 = 2

n mod 5 = 4

n mod 6 = 5

n mod 7 = 0

    我们从最后一项可以判断出，阶梯总数一定是7的整数倍，因此我们初始化假设总阶数为7，如果查找的数不是，则在此基础上加上7.当找到后，退出。即找到我们想要的值，代码如下：

#include <stdio.h>

int jieti(void);

int main(int argc, char *argv[])
{
  int result = jieti();
  printf("the result of einstein's question is\n%d\n",result);
  return 0;
}

int jieti(void)
{
  int result = 7;
  while(1)
  {
    if((result%2 == 1) && (result%3 == 2) && (result%5 == 4) && (result%6 == 5))
      break;
    else
      result += 7;
  }
  return result;
}

peng@ubuntu:~/src/test/c/suanfa/miaoqu$ ./a.out 

the result of einstein's question is

119

------------------------------------------------------------------------

  感谢网友dreamfisk，goubao198562的留言，其实我是按照书上的代码，将程序调试通过，对于dreamfisk提供的代码，我开始看不懂，经过goubao198562的解释，现在明白了：因为阶梯的总数分别除以2，3，5，6余数分别为1，2，4，5。这这个数一定是2,3,5,6最小公倍数值少一，才会出现余数分别为1，2，4，5的现象。我们可以很快求出2,3,5,6的最小公倍数数为30，因此初始化值为30 - 1 = 29。所以就剩下一项了，就是和7求余的余数为0。如果不是，则将数值加30，去寻找这个数，代码如下：

#include <stdio.h>

int jieti(void);

int main(int argc, char *argv[])
{
  int result = jieti();
  printf("the result of einstein's question is\n%d\n",result);
  return 0;
}

int jieti(void)
{
  int result = 29;
  while(1)
  {
    if(result%7 == 0)
      break;
    else
      result += 30;
  }
  return result;
}