一道算法题，求最优解法？

hot_ice

#include <iostream.h>
#include <math.h>

int main(int argc, char* argv[])
{
const int n = 200;
float r = 0;

for ( int i = 3; i < n; i += 2) {
   r = sqrt(2 * i * i - 1);
   if ( r == int(r) )
      cout << -(1 - r ) / 2 << " " << -(1 - r) / 2 + 1 << " " << i << endl;
}

   getchar();
    return 0;
}

有2个问题
1.浮点数相等比较
2.如果r-1不能被2整除

hot_ice

原帖由 ypxing 于 2008-4-23 08:57 发表
讨论具有这种性质的勾股数的帖子有不少，可以搜索一下

http://tieba.baidu.com/f?kz=337215336

1 勾股数  
象（3、4、5）、（20、21、29）、（119、120、169）这样的勾股数组中，（3、4）、（20、21）、（119、120）都可以表示成（A、A+1）的形式。如果我们设最小的A1=3，那么次小的A2=20，A3=119，A4=696，A5=4059，A6=23660；我们看从A1-A6这6个数的最后一位数字是：3、0、9、6、9、0。现在看第二组6个数，即A7=137903，A8=803760，A9=4684659，A10=27304196，A11=159140519，A12=927538920；这组数的最后一位数字是：3、0、9、6、9、0。再向下考察同样存在这个数组，即每6组数的最后一位数字顺序为（309690）。   
如果我们考察连续勾股数A（N）序列中的倒数第二个数字，我们可以得到一个更长的循环节，那是：（021956065912009978043934087990），这是个30位的循环节，其中包括2个对称节。第一部分是（0219560659120），以中间的0为界，两边对称；第二部分是（09978043934087990），以中间的9为界，两边对称。   
相信如果考察这个数组的倒数第三个数字，也会有同样的规律存在，可惜的是我手上没有这么大的连续勾股数表了。我猜测第三位数字的循环节在150位上。同样我们还可以猜测，是否每一位数字上都存在着循环节呢？   
践履尘扬   


  
作者： 222.173.17.*  2008-3-11 19:49 　 回复此发言   

--------------------------------------------------------------------------------

2 回复：勾股数  
的确是一个值得思考的问题  

  
作者： kindtiger17   2008-3-11 19:52 　 回复此发言   

--------------------------------------------------------------------------------

3 回复：勾股数  
又是数论  

贴子相关图片:

作者： 19910620   2008-3-11 19:55 　 回复此发言   

--------------------------------------------------------------------------------

4 回复：勾股数  
0,1,1也是一组勾股数,而且是第一组.  
个位的循环节是6位的,即030969.  
十位的循环节是30位的.  
百位上的循环节我已经计算出是300位的.  
千位上的循环节是3000位的.  
万位上的循环节是30000位的.  
十万位上的循环节是300000位的.  
由此我的推论是:以后每个数字位上出现的循环节都是其数字位所在幂的3倍  
践履尘扬.  

  
作者： 58.14.224.*  2008-3-15 14:59 　 回复此发言   

--------------------------------------------------------------------------------

5 回复：勾股数  
LS,个位  

  
作者： 218.91.98.*  2008-3-15 15:24 　 回复此发言   

--------------------------------------------------------------------------------

6 回复：勾股数  
百万位上的循环节确实是以300万为单位进行循环的.
这样我可以猜测:存在整数N,使得当M趋向任意大时,总有A=10(M)*N,(M为10的幂次);与A+1两数为连续勾股数.
践履尘扬.

wxycyel

这也只是猜测,并没有给出证明来.

hot_ice

原帖由 ypxing 于 2008-4-17 16:57 发表
其实很想证明：
(a1, b1, c1)
(a2, b2, c2)
(a3, b3, c3)

c3/c2 > c2/c1 > 5

没证出来

到目前为止你的猜测是对的
3         4         5         Cn/Cn-1
20         21         29         5.800000000000000
119         120         169         5.827586206896550
696         697         985         5.828402366863910
4059         4060         5741         5.828426395939090
23660         23661         33461         5.828427103292110
137903         137904         195025         5.828427124114640
803760         803761         1136689         5.828427124727600
4684659         4684660         6625109         5.828427124745640
27304196         27304197         38613965         5.828427124746170
159140519         159140520         225058681         5.828427124746190
927538920         927538921         1311738121         5.828427124746190

cugb_cat

原帖由 wxycyel 于 2008-4-23 09:39 发表
这也只是猜测,并没有给出证明来.

去找陈景润的《初等数论》看看。

hot_ice

c/a的极限应该是根号2

hot_ice

原帖由 liuke432 于 2008-4-17 13:35 发表
有一种数组(a,b,c)，满足条件: a*a+b*b=c*c和b=a+1。例如（3,4,5)。
用程序找出指定范围(1

n^2+(n+1)^2 为完全平方数问题的前 100个解 [帖号 #1089831] 2005-07-16 16:20  
  Idealguy
发帖数： 1265
注册时间： 2001-05
地区： 上海 注册用户  

参见 http://sq.k12.com.cn/bbs/index.p ... ;start=60#msg_num_7

利用已发现的规律（解的分布很有规律，相邻两个解的比值趋向于一个常数：5.82...），可轻易地求得（只要计算机足够强) 所有的解！！


01,3
02,20
03,119
04,696
05,4059
06,23660
07,137903
08,803760
09,4684659
10,27304196
11,159140519
12,927538920
13,5406093003
14,31509019100
15,183648021599
16,1070379110496
17,6238626641379
18,36361380737780
19,211929657785303
20,1235216565974040
21,7199369738058939
22,41961001862379596
23,244566641436218639
24,1425438846754932240
25,8308066439093374803
26,48422959787805316580
27,282229692287738524679
28,1644955193938625831496
29,9587501471344016464299
30,55880053634125472954300
31,325692820333408821261503
32,1898276868366327454614720
33,11063968389864555906426819
34,64485533470821007983946196
35,375849232435061491997250359
36,2190609861139547943999555960
37,12767809934402226172000085403
38,74416249745273809088000956460
39,433729688537240628356005653359
40,2527961881478169961048032963696
41,14734041600331779137932192128819
42,85876287720512504866545119809220
43,500523684722743250061338526726503
44,2917265820615946995501486040549800
45,17003071238972938722947577716572299
46,99101161613221685342183980258883996
47,577603898440357173330156303836731679
48,3366522229028921354638753842761506080
49,19621529475733170954502366752732304803
50,114362654625370104372375446673632322740
51,666554398276487455279750313289061631639
52,3884963735033554627306126433060737467096
53,22643228011924840308557008285075363170939
54,131974404336515487224035923277391441558540
55,769203198007168083035658531379273286180303
56,4483244783706493010989915264998248275523280
57,26130265504231789982903833058610216366959379
58,152298348241684246886433083086663049926232996
59,887659823945873691335694665461368083190438599
60,5173660595433557901127734909681545449216398600
61,30154303748655473715430714792627904612107953003
62,175752161896499284391456553846085882223431319420
63,1024358667630340232633308608283887388728479963519
64,5970399843885542111408395095857238450147448461696
65,34798040395682912435817061966859543312156210806659
66,202817842530211932503493976705300021422789816378260
67,1182109014785588682585146798264940585224582687462903
68,6889836246183320163007386812884343489924706308399160
69,40156908462314332295459174079041120354323655162932059
70,234051614527702673609747657661362378636017224669193196
71,1364152778703901709363026771889133151461779692852227119
72,7950865057695707582568412973673436530134660932444169520
73,46341037567470343786047451070151486029346185901812790003
74,270095360347126355133716293447235479645942454478432570500
75,1574231124515287787016250309613261391846308540968782632999
76,9175291386744600366963785564232332871431908791334263227496
77,53477517195952314414766463075780735836745144207036796731979
78,311689811788969286121634992890452082149038956450886517164380
79,1816661353537863402315043494266931757057488594498282306254303
80,10588278309438211127768625972711138460195892610538807320361440
81,61713008503091403364296712341999899004117867068734561615914339
82,359689772709110209058011648079288255564511309801868562375124596
83,2096425627751569850983773176133729634382949991742476812634833239
84,12218863993800308896844627408723089550733188640652992313433874840
85,71216758335050283530083991276204807670016181852175477067968415803
86,415081686016501392283659320248505756469363902472399870094376619980
87,2419273357763958070171871930214829731146167232982223743498291304079
88,14100558460567247028747572261040472630407639495420942590895371204496
89,82184077405639524102313561636028006051299669739543431801873935922899
90,479003905973269897585133797555127563677390378941839648220348244332900
91,2791839358433979861408489223694737376013042603911494457520215530074503
92,16272032244630609270865801544613296692400865244527127096900944936114120
93,94840354109349675763786320043985042778392148863251268123885454086610219
94,552770092411467445311852118719296959977952027934980481646411779583547196
95,3221780200359454996107326392271796717089320018746631621754585223414672959
96,18777911109745262531332106234911483342557968084544809248881099560904490560
97,109445686458112120191885311017197103338258488488522223871532012142012270403
98,637896207638927458619979759868271136686992962846588533980310973291169131860
99,3717931559375452631527993248192429716783699288591008980010333827605002520759
100,21669693148613788330547979729286307164015202768699465346081691992338845992696

b:=a(100)/a(99)=5.8284271247461900976033774484193961571393437507538961463533594759814649569248634


第1000个解为：

                                  214825766352939481138240636295284988465589643358888221139785196264
2390678121914097981429443513773527479556605895589581969722834819148766221575649903025296824013027053
7516476227744837681671428022539675427226992392334093936743352819024344216966262222014880062404059163
3436084648492456901070547402961432943754468150693938637958279916435857068154570972887316105661559725
0968698587561800593385995333213808340692444671734708086807865220607992256188662676376207817322573231
1655570931119246761478394826635187895655374886074293056011252240450551827861319265459837406850821843
2073418422260910006328229779330696389048979343336633973739891718384698757509029366681375514440525751
1089107616790419169121959112713807581631837777050921853055164073097413558474288667196935426115027696

有766位

相邻解的比值为：
5.82842712474619009760337744841939615713934375075389614635335947598146495692421407770077506865528314
5470027692461824594049849672111701474425288242994199871662826445331855011185511599901002305564121142
9402191199432119405490691937240294570348372817783972191046584609686174286429016795252072559905028159
7937450679309266361765928124123051670479010949150057551992345967115044067506371402270874920681699769
4320773799941398009630061088055580632908495646136985873837243161156926223193337426026031237137974474
4705770185297224989954308436668408571372120293649441542871709748311314139355307440452970894031717603
2415169498453144520041711689330429167977878887418531836006227764929363141652602011897174080063729606
84389794556581282090145273762627479710512234644080490182455400453947755054694658

[更新： 2005-07-16 16:28]



--------------------------------------------------------------------------------
理想主义分子Idealguy
违规帖举报
      


回复： n^2+(n+1)^2 为完全平方数问题的前 100个解 [帖号 #1089918] 2005-07-16 17:15  
Joseph
发帖数： 1139
注册时间： 2004-09  注册用户  

这个问题很简单，满足n2+(n+1)2是完全平方数的全部整数解为
n=(p-1)/2，
其中
p+√2k=(1+√2)2t-1，
p、k都是整数，t为任意正整数。

违规帖举报
      


回复： n^2+(n+1)^2 为完全平方数问题的前 100个解 [帖号 #1089948] 2005-07-16 17:30  
Joseph
发帖数： 1139
注册时间： 2004-09  注册用户  

如果把p计算出来，就是
p=((1+√2)2t-1+(1-√2)2t-1)/2，
计算两个相邻的n的极限值就不是什么困难的事情了，其极限（后一n与前一n的比值）就是
3+2√2≈5.8284271247461900976。