爱因斯坦阶梯问题

  爱因斯坦曾经提出过这样一道有趣的数学题：有一个长阶梯，若每步上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

用“强”解：

#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; }

 转化为一道数学问题：有一个数除以2、3、4、5、6,余数都为1,除以7则无余数,这个数最小是多少?

 由 n mod 2 = 1

n mod 3 = 2 n mod 5 = 4

n mod 6 = 5

n mod 7 = 0

 以上我们可以得出一个结论，即n总是比2，3，5，6的公倍数小1，为什么呢？

 因为，我们通过上式，可以有 2|（n+1），3|（n+1）,5|（n+1）,6|（n+1），7|n

 可得，[2，3，5，6]|（n+1）

 即，2，3，5，6的最小公倍数可以整除n+1，而[2,3,5,6]=30

 所以30|n+1，由带余除法可以有，30q=n+1，=> n=30q-1(q为自然数且不为0)

 固有29+30*num=n  ==>  29+3030*3=7*19=119=n

 即n=119

#include <stdio.h> int upStair(void); int main(int argc, char *argv[]) { int result = upStair(); printf("the result of einstein's question is\n%d\n",result); return 0; } int upStair(void) { int result = 29; while(1) { if(result%7 == 0) break; else result += 30; } return result; }最后，其实中国剩余定理也能很轻松解决这类问题。