一个求完全平方数的算法
<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编辑过]
回复：（lvyehuaigu）一个求完全平方数的算法
这个算法效率高吗？可以和下面的算法比较一下<br><br>一般完全平均数采用的算法是<br>从1开始的n个奇数的和是一个完全平方数，n2―即1＋3＋5＋7＋…＋（2n-1）＝n2[此贴子已经被作者于2006-6-20 9:46:45编辑过]
<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>
页:
[1]