一个求完全平方数的算法

lvyehuaigu

<STRONG>一个求完全平方数的算法<br><br></STRONG>一个朋友给我出了个题，做了之后，感觉非常之妙，还没来得及思考其中奥妙呢，还是先将其记录下来再说吧！题目大致是这样叙述的：<br>    有100个人和100盏灯，并分别编号，灯开始都是灭的，从第一个人开始拉灯的开关，第i个人只拉编号为i的倍数的灯（比如第3个人只拉第3、6、9、...、99盏灯），求100个人都拉完相应的灯后，亮着的灯的编号是哪些？<br>    听了题之后，马上编了个very easy的程序，matlab代码如下：<br>function xiayu<br>%100个人100盏灯时的情况。<br>n=100<br>ren=1:n;<br>deng=-ones(1,n);<br>for i=1:n<br>    for j=i:i:n<br>            deng(j)=-deng(j);<br>    end<br>end<br>find(deng==1)<br>运行一下结果是：1     4     9    16    25    36    49    64    81   100<br>都是完全平方数，我马上意识到这是一个列举完全平方数的算法，而且算法的执行效率相当高。<br>   请问有谁明白其中的道理呢？或给出其数学证明！

[此贴子已经被作者于2006-6-20 14:22:05编辑过]

风花雪月

这个算法效率高吗？可以和下面的算法比较一下<br><br>一般完全平均数采用的算法是<br>从1开始的n个奇数的和是一个完全平方数，n2―即1＋3＋5＋7＋…＋（2n-1）＝n2

[此贴子已经被作者于2006-6-20 9:46:45编辑过]

lvyehuaigu

<P>    恩！是没办法和这个求和的效率比，错的太远了！看来那只能算作一个智利游戏了。呵呵！不过原理已经搞清楚！<BR>    其实问题可以转化为，一个数的所有约数，包括1和它本身的总的数目是奇数。<BR>而约数的个数有一个公式：<BR>对任意合数A，可以分解为几个质数的乘积<BR>A=(a^i)(b^j)........(z^k),其中a，b，.....z为质数，i，j，k分别为他们的指数，则对A它的所有约数个数N=(i+1)(j+1)....(k+1),如果满足题目意思，N为奇数，则ijk都必须是偶数。那么显然A是一个完全平方数。<BR></P>