首页 > 数学相关 > 数论应用 > 数论(1)-幸运数字
2014
03-31

数论(1)-幸运数字

幸运数也是属于整数的一个集合。来看下是幸运数是怎么生成的,大家就明白什么是幸运数了。

由一组由1开始的数列为例:

1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,17,18,19,……

先将数列中的第2n个数(偶数)删除,只留下奇数:

1,3,5,7,9,11,13,15,17,19,…………

将新数列的第3n个数删除:

1, 3, 7, 9, 13, 15, 19,….….

重复上一个过程,无限的循环。最后留下来的那些数字,就是幸运数。(这里说的幸运数和维基百科说的不一样)

问题:

给一个数n,判断n是否是一个幸运数字。

算法分析:

主要是递推,考虑数字n的位置变化。第一n轮删除时,n的位置即为n,结束后的位置即为 n-n/2, 依此类推下去即可。

#include <stdio.h>
#include <iostream>
using namespace std;
#define bool int

bool isLucky(int n)
{
  static int counter = 2;

  /* next_position 只是为了可读性,可以只用n */
  int next_position = n;
  if(counter > n)
    return 1;
  if(n%counter == 0)
    return 0;
 /*计算数字n的下一个位置*/
  next_position -= next_position/counter;
  counter++;
  return isLucky(next_position);
}

/*测试程序*/
int main()
{
  int x = 19;
  if( isLucky(x) )
    printf("%d is a lucky no.", x);
  else
    printf("%d is not a lucky no.", x);

}

参考:http://www.geeksforgeeks.org/fundamentals-of-algorithms/


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮