数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 编程擂台 › 平方数数字和
1 ...3456789101112... 18下一页
返回列表 发新帖
楼主: mathe

[擂台] 平方数数字和

[复制链接]
gxqcn
发表于 2008-7-11 08:44:25 | 显示全部楼层
原帖由 无心人 于 2008-7-11 08:09 发表
呵呵
你看看你程序的mark的全部输出
而不是部分结果哦


根据数论知识，一个整数的平方 mod 9 只能为 0、1、4、7 四类，
所以其它的本就不应有值。

不过，我还是不明白你说的 bug 是什么？
我觉得没有任何问题。

下面我将发一个改进版，可以搜索任意大范围内的值，
当然，依然是高度优化的。。。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 2008-7-11 08:47:56 | 显示全部楼层

可以搜索任意大范围的程序

下面的代码可以完全搜索 10^(4*LIMBS) 内的数字：
推荐
  1. #include <stdlib.h>
  2. #include <stdio.h>

  4. #include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h"    // 公共接口

  6. #pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
  7. #pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )


  10. #define TEN_POW2    100UL
  11. #define TEN_POW4    10000UL

  13. #define LIMBS       5

  15. int main( void )
  16. {
  17.     UINT32 table[ TEN_POW4 ];
  18.     UINT32 index[ LIMBS + 1 ], value[ LIMBS ], delta[ LIMBS ];
  19.     BYTE exist[ 9*4*LIMBS ];
  20.     UINT32 * p = table;

  22.     UINT32 i, m, s;
  23.     UINT32 i2, i3, i4, s2, s3;

  25.     HugeCalc::EnableTimer();
  26.     HugeCalc::ResetTimer();

  28.     for ( i4 = 0; i4 < 10; ++i4 )
  29.     {
  30.         for ( i3 = 0; i3 < 10; ++i3 )
  31.         {
  32.             s3 = i4 + i3;
  33.             for ( i2 = 0; i2 < 10; ++i2 )
  34.             {
  35.                 s2 = s3 + i2;
  36.                 for ( i = 0; i < 10; ++i )
  37.                 {
  38.                     *p++ = s2 + i;
  39.                 }
  40.             }
  41.         }
  42.     }

  44.     memset( index, 0, sizeof( index ));
  45.     memset( value, 0, sizeof( value ));
  46.     memset( delta, 0, sizeof( delta ));
  47.     memset( exist, 0, sizeof( exist ));

  49.     delta[ 0 ] = 1;
  50.     m = 0;
  51.     for ( ; ; )
  52.     {
  53.         i = -1;
  54.         while ( TEN_POW2 == ++index[ ++i ] )
  55.         {
  56.             index[ i ] = 0;
  57.         }

  59.         if ( m < i )
  60.         {
  61.             m = i;

  63.             printf( "\n****** Searched all perfect squares less then 10^%u ******\n\n", 4*m );

  65.             if ( LIMBS == i )
  66.             {
  67.                 break;
  68.             }
  69.         }

  71.         s = 0;
  72.         for ( i = 0; i <= m; ++i )
  73.         {
  74.             value[ i ] += delta[ i ];
  75.             if ( value[ i ] >= TEN_POW4 )
  76.             {  /* 当 i==m 时不会进入，因此时平方根<100^(m+1) */
  77.                 value[ i ] -= TEN_POW4;
  78.                 ++value[ i + 1 ];
  79.             }

  81.             s += table[ value[ i ] ];
  82.         }

  84.         if ( 0 == exist[ s ] )
  85.         {
  86.             exist[ s ] = 1;

  88.             printf( HugeCalc::GetTimerStr( FT_HHMMSS_ms ));
  89.             printf( "\tX = %u\t\tS = %u", s, value[ --i ] );
  90.             while ( 0 != i )
  91.             {
  92.                 printf( "%04u", value[ --i ] );
  93.             }
  94.             printf( "\n" );
  95.         }

  97.         delta[ 0 ] += 2;

  99.         i = 0;
  100.         while ( delta[ i ] >= TEN_POW4 )
  101.         {
  102.             delta[ i ] -= TEN_POW4;
  103.             ++delta[ ++i ];
  104.         }
  105.     }


  108.     printf( "\nComputation took %s\n\n", HugeCalc::GetTimerStr( FT_DOT06SEC_s ) );

  110.     return 0;
  111. }
复制代码
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 2008-7-11 08:49:31 | 显示全部楼层
运行结果如下：
00:00:00.000    X = 1           S = 1
00:00:00.000    X = 4           S = 4
00:00:00.000    X = 9           S = 9
00:00:00.000    X = 7           S = 16
00:00:00.000    X = 13          S = 49
00:00:00.001    X = 10          S = 64
00:00:00.001    X = 16          S = 169
00:00:00.001    X = 19          S = 289
00:00:00.001    X = 18          S = 576
00:00:00.001    X = 22          S = 1849
00:00:00.001    X = 27          S = 3969
00:00:00.002    X = 25          S = 4489
00:00:00.002    X = 31          S = 6889

****** Searched all perfect squares less then 10^4 ******

00:00:00.002    X = 28          S = 17956
00:00:00.002    X = 34          S = 27889
00:00:00.002    X = 36          S = 69696
00:00:00.003    X = 40          S = 97969
00:00:00.003    X = 37          S = 98596
00:00:00.003    X = 43          S = 499849
00:00:00.003    X = 46          S = 698896
00:00:00.005    X = 45          S = 1887876
00:00:00.005    X = 49          S = 2778889
00:00:00.005    X = 52          S = 4999696
00:00:00.005    X = 54          S = 9696996
00:00:00.006    X = 55          S = 19998784
00:00:00.008    X = 58          S = 46689889
00:00:00.008    X = 61          S = 66699889
00:00:00.008    X = 63          S = 79869969

****** Searched all perfect squares less then 10^8 ******

00:00:00.008    X = 64          S = 277788889
00:00:00.010    X = 67          S = 478996996
00:00:00.010    X = 70          S = 876988996
00:00:00.011    X = 73          S = 1749999889
00:00:00.012    X = 72          S = 3679999569
00:00:00.013    X = 76          S = 5599977889
00:00:00.014    X = 79          S = 7998976969
00:00:00.014    X = 81          S = 8998988769
00:00:00.016    X = 82          S = 17999978896
00:00:00.017    X = 85          S = 36799899889
00:00:00.020    X = 88          S = 88998998929
00:00:00.027    X = 90          S = 297889998849
00:00:00.027    X = 91          S = 299879997769
00:00:00.037    X = 94          S = 897977978689
00:00:00.038    X = 97          S = 975979998889

****** Searched all perfect squares less then 10^12 ******

00:00:00.060    X = 100         S = 2699997789889
00:00:00.072    X = 99          S = 3957779999889
00:00:00.106    X = 103         S = 9879498789889
00:00:00.108    X = 106         S = 9998768898889
00:00:00.186    X = 108         S = 29998985899689
00:00:00.316    X = 109         S = 85986989688889
00:00:00.337    X = 112         S = 97888999968769
00:00:00.674    X = 115         S = 386999898769969
00:00:00.713    X = 117         S = 429998989997889
00:00:00.835    X = 118         S = 578889999977689
00:00:01.035    X = 121         S = 898999897988929
00:00:01.483    X = 124         S = 1959999889996996
00:00:02.012    X = 127         S = 3699998989898689
00:00:02.753    X = 126         S = 6788999798879769
00:00:03.290    X = 130         S = 9895699989899689

****** Searched all perfect squares less then 10^16 ******

00:00:07.093    X = 133         S = 38896878989988889
00:00:07.104    X = 136         S = 38999699989995889
00:00:09.566    X = 135         S = 67699789959899889
00:00:16.382    X = 139         S = 188997899869998769
00:00:20.072    X = 142         S = 279869897899999969
00:00:26.956    X = 144         S = 498999778899898896
00:00:38.234    X = 148         S = 989879999979599689
00:00:52.898    X = 145         S = 1877896979979898969
00:01:34.317    X = 153         S = 5899989587897999889
00:01:42.666    X = 151         S = 6979497898999879969
00:01:56.083    X = 154         S = 8899988895999696889
00:03:30.418    X = 157         S = 28979978999958969889
00:05:47.960    X = 160         S = 78897999969769888996
00:06:07.529    X = 162         S = 87989899898866889889

****** Searched all perfect squares less then 10^20 ******


Computation took 392.264510 s

Press any key to continue


可以把代码中的 LIMBS 适当修改成更大的值，即可搜索更大范围内的数据。
想多大都行，反正中途即会输出计算结果

评分

参与人数 1威望 +1 鲜花 +1 收起 理由
mathe + 1 + 1 精品文章

查看全部评分

毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2008-7-11 09:58:11 | 显示全部楼层
我机器在挂着程序运行呢
我在外边
新结果等回家去贴上来
GxQ的正好和我的相互验证
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2008-7-11 10:04:15 | 显示全部楼层


GxQ考虑加上状态保存否？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 2008-7-11 10:04:52 | 显示全部楼层
你可与我的 72# 对比一下，看谁的高效？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 2008-7-11 10:06:23 | 显示全部楼层
原帖由 无心人 于 2008-7-11 10:04 发表


GxQ考虑加上状态保存否？


没有太大必要啊。
即便保存状态，也只需保存那几个数组，以及 m 即可（m 也可由 index[] 计算出），所需空间非常小。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 2008-7-11 10:49:54 | 显示全部楼层
从现有数据来看，十个阿拉伯数字仅“0”从未出现于S中，
请问，S中可能出现某位数字为“0”吗？对应的最小X=?
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2008-7-11 11:32:42 | 显示全部楼层
171    00000000000789899899796987988996
169    00000000000969988797999759789889
172    00000000003599979999987777888889
175    00000000004899976999986989889796
178    00000000008889998799995887887889
180    00000000009899698989999989958489
181    00000000017989999975899879969889
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2008-7-11 11:51:41 | 显示全部楼层
呵呵
我猜测是木有可能出现0
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

1 ...3456789101112... 18下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-5-4 00:27 , Processed in 0.046501 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表