最小无法表达的正整数

无心人

你什么时候想明白，不用考虑括号了 你才能参与这个题目的 这个题目根本不用考虑括号的问题！！ 当然，不是不用括号 PS: 我的那个估计是很不准确的

mathe

我不知道你怎么搜索的(没有看你的代码),但是我简单修改了一下我以前的代码,直接试着搜索n=11时只包含+,-,*的所有表达式,现在运行了一天左右,搜索出所有结果652566以前的表达式,总共已经搜索了233937173249个表达式.而程序还在继续运行中,也许还要运行几天. Searching for 536423 now Time cost 88979,searched expressions:233472033610 Searching for 652567 now Time cost 89148,searched expressions:233937173249

mathe

而这个程序显然将不能对付n=12的情况

无心人

不解决状态保存问题 根本12的无法做 11的你能保证不停电么？ 我那个新程序我想改成C语言 有1000GB NTFS分区应该可以运行出12的结果 中间过程完全可以做到保存状态的 只要连续7天不停电就可以了

mathe

下面这个程序计算n=9只需要3分钟左右,不知道计算n=11需要多长时间(只考虑+,-,*三种操作符)

2. // unreach.cpp : Defines the entry point for the console application.
3. //
5. #include "stdafx.h"
7. #include <algorithm>
8. #include <iostream>
9. #include <vector>
10. #include <time.h>
11. #include <string>
12. #include <set>
13. #include <stdio.h>
15. #ifdef _WIN32
16. typedef __int64 longlong;
17. #else
18. typedef long long longlong;
19. #endif
20. using namespace std;
22. #ifdef _DEBUG
23. #include <assert.h>
24. #define ASSERT(x) assert(x)
25. #else
26. #define ASSERT(x)
27. #endif
28. #define MAX_NUM 11
29. //#define ALL_VALUES
30. #define SMALL_SEARCH
31. #define SEARCH_VALUE 11
33. //enlarge CACHE_LIMIT so that some expression will be saved in memory. This
34. //will speed the program,
35. //but then we could not print the correct expression by expression() function.
36. //CACHE_LIMIT should be no more than 8. I found that the speed will drop when
37. //CACHE_LIMIT is too large
38. #define CACHE_LIMIT 8
39. #define MAX_BUF_SIZE 1088640000
40. vector<bool> visited(MAX_BUF_SIZE,false);
41. int cur_scan=1;
43. #if CACHE_LIMIT==0
44. //#define DISPLAY_NEW_VISIT
45. //We could not define macro DISPLAY_NEW_VISIT when CACHE_LIMIT is non-zero, since we could not dump out expression when only result of sub-tree is cached (and sub-tree not available)
46. //define CACHE_LIMIT to 0 and define DISPLAY_NEW_VISIT could dump out all the first expression to reach any integer number
47. #endif
49. #ifdef SMALL_SEARCH
50. typedef int number;
51. #define INTEGER(x) ((x)>=0?(x):-(x))
52. #define IS_INTEGER(x) true
53. #define IS_VALID(x) true
54. #else
55. #define INTEGER(x) (x).get_integer()
56. #define IS_INTEGER(x) (x).is_integer()
57. #define IS_VALID(x) (x).is_valid()
58. class number{
59. int up;
60. int down;
61. public:
62. number(const number& n):up(n.up),down(n.down){}
63. number(int n=0):up(n),down(1){}
64. number& operator+=(const number& n);
65. number& operator-=(const number& n);
66. number& operator*=(const number& n);
67. number& operator/=(const number& n);
68. bool is_zero()const{return down!=0&&up==0;}
69. bool is_valid()const{return down!=0;}
70. bool is_one()const{return down!=0&&up==down;}
71. bool operator==(const number& n)const{return
72. is_valid()&&n.is_valid()&&n.down*up==n.up*down;}
73. bool operator<(const number& n)const;
74. bool operator>(const number& n)const{return n<*this;}
75. bool operator<=(const number& n)const{return !(*this>n);}
76. bool operator!=(const number& n)const{return !(n==*this);}
77. bool operator>=(const number& n)const{return !(*this<n);}
78. number operator+(const number& n)const{number m(*this);return m+=n;}
79. number operator-(const number& n)const{number m(*this);return m-=n;}
80. number operator*(const number& n)const{number m(*this);return m*=n;}
81. number operator/(const number& n)const{number m(*this);return m/=n;}
82. bool is_integer()const{return down!=0&&up%down==0;}
83. int get_integer()const{if(is_integer())return up/down;else return -1;}
84. number& operator=(int n){up=n;down=1;return *this;}
85. int get_up()const{return up;}
86. int get_down()const{return down;}
87. };
89. number& number::operator +=(const number& n)
90. {
91. up=up*n.down+down*n.up;
92. down*=n.down;
93. return *this;
94. }
96. number& number::operator -=(const number& n)
97. {
98. up=up*n.down-down*n.up;
99. if(up<0)up=-up;
100. down*=n.down;
101. return *this;
102. }
104. number& number::operator *=(const number& n)
105. {
106. up*=n.up;
107. down*=n.down;
108. return *this;
109. }
111. number& number::operator /=(const number& n)
112. {
113. down*=n.up;
114. up*=n.down;
115. return *this;
116. }
118. bool number::operator <(const number &n)const
119. {
120. return up*n.down<n.up*down;
121. }
122. #endif
123. /*iterator to enumerate the partition of n different objects into m groups,where m is a varialbe so that the iterator will enumerate all m in range [2,n]
124. * and sub-iterator split_iterator spliter is used to enumerator numbers of objects in each groups
125. */
126. class select_iterator{
127. int n;//total n element;
128. int m;//max group id; That's group 1<<8,2<<8,...,m<<8; m should be no less than 2.
129. //The select_iterator is used to split n elements into groups.
130. int select_array[MAX_NUM];///tells which group each number is located (It is select_array[x]>>8) and the order of the number inside the group (select_array[x]&255)
131. int sub_size[MAX_NUM]; ///sub_size[x] provides the number of elements of all groups whose group id no more than x
132. class split_iterator{///iterator to partition 'size' same objects into several groups (so only number of objects in each group is considered)
133. int split_array[MAX_NUM];///number of objects in each group
134. int last_index;///number of group - '1'
135. public:
136. split_iterator(int size)
137. {
138. ASSERT(size<=MAX_NUM);
139. if(size==1)
140. {
141. last_index=0;
142. split_array[0]=1;
143. }
144. else
145. {///Usually, we need partition data into at least two groups.
146. last_index=1;
147. split_array[0]=size-1;
148. split_array[1]=1;
149. }
150. }
151. bool inc()///Move to the next partition
152. {
153. int i;
154. ASSERT(last_index<MAX_NUM);
155. for(i=last_index;i>=0;--i)
156. {
157. if(split_array[i]>=2)
158. break;
159. }
160. if(i==-1)
161. {
162. int size=0;
163. for(i=0;i<=last_index;++i)
164. size+=split_array[i];
165. if(size==1)
166. {
167. last_index=0;
168. split_array[0]=1;
169. }
170. else
171. {
172. last_index=1;
173. split_array[0]=size-1;
174. split_array[1]=1;
175. }
176. return false;//end of search.
177. }
178. else
179. {
180. int total;
181. int last;
182. last=--split_array[i];
183. total=last_index-i+1;
184. while(total>=last){
185. split_array[++i]=last;
186. total-=last;
187. }
188. if(total>0){
189. split_array[++i]=total;
190. }
191. last_index=i;
192. }
193. return true;
194. }
195. friend class select_iterator;
196. }spliter;
197. void init_from_spliter();
198. public:
199. select_iterator(int size);
200. bool inc();
201. int get_sub_group_count()const{return spliter.last_index+1;}
202. int get_sub_size(int group_id)const{return sub_size[group_id/256-1];}
203. int get_group_id(int num)const{return select_array[num];}
204. int get_main_id(int group_id)const{return group_id/256-1;}
205. int get_sub_id(int group_id)const{return group_id%256;}
206. int split_size(int i)const{return spliter.split_array[i];}
207. int size()const{return n;}
208. #ifdef _DEBUG
209. void print()const;
210. #endif
211. };
213. select_iterator::select_iterator(int size):spliter(size)
214. {
215. init_from_spliter();
216. }
218. void select_iterator::init_from_spliter()
219. {
220. int i,prev,sg,t;
221. n=0,m=0;
222. prev=-1;
223. for(i=0;i<=spliter.last_index;++i)
224. {
225. if(spliter.split_array[i]!=prev)
226. {
227. sub_size[m]=spliter.split_array[i];
228. m++;
229. sg=0;
230. }
231. else
232. sg++;
233. for(t=0;t<spliter.split_array[i];t++)
234. {
235. select_array[n++]=m*256+sg;
236. }
237. prev=spliter.split_array[i];
238. }
239. }
241. bool select_iterator::inc()
242. {
243. int i;
244. int buf[MAX_NUM];
245. bool result;
246. do
247. {
248. result = next_permutation(select_array,select_array+n);///permutate all numbers until
249. if(!result)
250. break;
251. memset(buf,-1,sizeof(buf));
252. for(i=0;i<n;++i){//fill result into buf
253. int t=get_main_id(select_array[i]);
254. int q=get_sub_id(select_array[i]);
255. if(buf[t]<0)
256. buf[t]=q;
257. else
258. if(buf[t]>q)//invalid, all numbers in same subgroup should be ordered. Maybe we could optimize the code further
259. break;
260. }
261. if(i==n)
262. break;
263. }while(true);
264. if(!result){///We need increase spliter when all permutation of data are searched
265. if(!spliter.inc())
266. {//set end.
267. init_from_spliter();
268. return false;
269. }
270. else
271. {
272. init_from_spliter();
273. }
274. }
275. return true;
276. #if 0
277. for(i=n-1;i>0;--i)
278. {
279. if(select_array[i]>select_array[i-1])
280. {
281. if((select_array[i]/256)==(select_array[i-1]/256))
282. {//if in the same group.
283. int j;
284. // if(sub_size[select_array[i]/256-1]==1)
285. // continue;
286. for(j=i-2;j>=0;--j)
287. {
288. if(select_array[j]==select_array[i-1])
289. break;
290. }
291. if(j>=0)//if found one.
292. break;
293. }
294. else
295. break;
296. }
297. }
298. if(i==0)//not found
299. {
300. if(!spliter.inc())
301. {//set end.
302. init_from_spliter();
303. return false;
304. }
305. else
306. {
307. init_from_spliter();
308. }
309. }
310. else
311. {
312. int tmp=select_array[i];
313. select_array[i]=select_array[i-1];
314. select_array[i-1]=tmp;
315. if(i<n-2)
316. {
317. sort(select_array+i+1,select_array+n);
318. }
319. }
320. return true;
321. #endif
322. return result;
323. }
326. /*Expressions are represented by the tree iterator here.
327. *There're two different kinds of trees according to the topmost level operator.
328. * the field get_prod is used to indicate whether the topmost level operators're mulitplication/division or add/sub.
329. * For example, expression 4*(-3)/(1+2*5) is an expression whose topmost level operators are {*,/}
330. * and it has three children, the first is 4, the second is (-3) and the third is expression 1+2*5
331. * and similarly the topmost level operators of 1+2*5 is {+}. It has two children, the first is 1 and the second 2*5, etc
332. * In each "tree_iterator" (a node of the tree), a spliter field is used to determine how much children nodes there're
333. * and how much operands there're in the (sub-)expression and how much topmost operators there're. And how those operands are partitioned to children.
334. * For example, if the expression is 4*(-3)/(1+2*5), there're totoal 5 operands {-3,1,2,4,5} and 2 topmost operators so that operands are partition into 3 group.
335. * The first child contains {4}, the second contans {-3}, the third contains {1,2,5}
336. * Please pay attention that change ordering of children does not change the value as soon as we change the correspondent bits in pattern.
337. * So the spliter will make sure that all groups are ordered according to number of elements to avoid those unnecessary recomputation
338. * And the pattern will be increased by 2 instead of 1 when get_prod==0. It means that no '-' will be added to the first child.
339. * so that for operands set {a,b} with get_prod==0, we will only enumerate expression a+b and a-b. (b-a will not be enumerated)
340. * And for the final result, as soon as we could reach the result -x<0, it means we could also reach x by exchange ordering of some operands.
341. */
342. class tree_iterator{
343. select_iterator spliter;
344. tree_iterator *next_sibling; ///pointer to the next sibling (the node whose has same parent node with this_node), NULL if it is the last child of the parent
345. tree_iterator *first_child; ///pointer to the first child of the node, NULL if it is leaf. So we could use first_child->next_sibling to get the second child node
346. tree_iterator *current_child_iterator;///A temporary pointer used when visiting the tree. (Maybe we should not define it here)
347. int get_prod; ///when get_prod!=0, all topmost operators are either * or /; otherwise all topmost operators are either + or -.
348. number valued; ///field used to save the value of the expression.
349. int data[MAX_NUM]; ///field to save all operands used by all leaf nodes. so data[]={2,-3,1,2,5} for expression 2*(-3)/(1+2*5)
350. int pattern; ///Used to determine whether an operator is * or / when get_prod!=0 and wheter an operator is + or - when get_prod==0.
351. ///pattern will be treated as a bit vector. 1 for * or + and 0 for / or -. refer to function set_values();
352. void build_tree(); ///Function to build the tree for an expression
353. void clear_child(); ///Function to remove all children(to clear the node)
354. void set_values(); ///set the value of the expression according to the value of children
355. int cached;
356. int finished_cached;
357. vector<number> caches;
358. int start_cache_id;
359. int cur_cache_id;
360. string prod_expression()const; ///get the expression in string format when get_prod!=0
361. string sum_expression()const; ///get the expression in string format when get_prod==0
362. bool no_cache_inc(); ///enumerate next expression
363. void no_cache_build_tree(); ///entry function to build the tree for first expression
364. void create_cache_file();
365. void read_cache_file(int offset);
366. public:
367. bool inc();
368. tree_iterator(int n,int d[],int prod);
369. int size()const{return spliter.get_sub_group_count();}
370. ~tree_iterator(){clear_child();}
371. const number& get_value()const{return valued;}
372. string get_pattern()const;
373. bool debug_sum(){return true;}
374. bool debug_prod(){return false;}
375. string expression()const{if(get_prod)return prod_expression();else return
376. sum_expression();}
377. };
379. #define BUFFER_LEN 1024
380. number buffer[BUFFER_LEN];
381. string tree_iterator::prod_expression()const
382. {
383. if(first_child==NULL)
384. {
385. char buf[10];
386. sprintf(buf,"%d",INTEGER(valued));
387. return string(buf);
388. }
389. else
390. {
391. int i;
392. string s;
393. bool first=true;
394. tree_iterator *child=first_child;
395. for(i=0;i<spliter.get_sub_group_count();++i)
396. {
397. if(pattern&(1<<i)){
398. if(!first)
399. s+='*';
400. first=false;
401. s+=child->sum_expression();
402. }
403. child=child->next_sibling;
404. }
405. child=first_child;
406. for(i=0;i<spliter.get_sub_group_count();++i)
407. {
408. if(!(pattern&(1<<i))){
409. s+='/';
410. s+=child->sum_expression();
411. }
412. child=child->next_sibling;
413. }
414. return s;
415. }
416. }
418. string tree_iterator::get_pattern()const
419. {
420. if(first_child==NULL)
421. {
422. char buf[10];
423. sprintf(buf,"%d",INTEGER(valued));
424. return string(buf);
425. }
426. else
427. {
428. int i;
429. string s;
430. tree_iterator *child=first_child;
431. s+='[';
432. for(i=0;i<spliter.get_sub_group_count();++i)
433. {
434. s+=child->get_pattern();
435. child=child->next_sibling;
436. }
437. s+=']';
438. return s;
439. }
440. }
442. string tree_iterator::sum_expression()const
443. {
444. if(first_child==NULL)
445. {
446. char buf[10];
447. sprintf(buf,"%d",INTEGER(valued));
448. return string(buf);
449. }
450. else
451. {
452. int i;
453. string s;
454. bool first=true;
455. tree_iterator *child=first_child;
456. s+='(';
457. for(i=0;i<spliter.get_sub_group_count();++i)
458. {
459. if(pattern&(1<<i)){
460. if(!first)
461. s+='+';
462. first=false;
463. s+=child->prod_expression();
464. }
465. child=child->next_sibling;
466. }
467. child=first_child;
468. for(i=0;i<spliter.get_sub_group_count();++i)
469. {
470. if(!(pattern&(1<<i))){
471. s+='-';
472. s+=child->prod_expression();
473. }
474. child=child->next_sibling;
475. }
476. s+=')';
477. return s;
478. }
479. }
481. bool tree_iterator::no_cache_inc()
482. {
483. if(get_prod)
484. pattern++;
485. else
486. pattern+=2;
487. #ifndef SMALL_SEARCH
488. if(pattern<(1<<size()))
489. {
490. set_values();
491. }
492. else
493. #else
494. if(!get_prod&&(pattern<(1<<size()))){
495. set_values();
496. }
497. else
498. #endif
499. {
500. while(current_child_iterator&&!current_child_iterator->inc())
501. current_child_iterator=current_child_iterator->next_sibling;
502. if(current_child_iterator)
503. {
504. current_child_iterator=first_child;
505. pattern=1;
506. set_values();
507. }
508. else
509. {
510. if(spliter.inc())
511. {
512. no_cache_build_tree();
513. }
514. else
515. {
516. no_cache_build_tree();
517. return false;
518. }
519. }
520. }
521. return true;
522. }
524. bool tree_iterator::inc()
525. {
526. if(finished_cached)
527. {
528. ++cur_cache_id;
529. if(cur_cache_id>=caches.size())
530. {
531. if(caches.size()==BUFFER_LEN){
532. read_cache_file(start_cache_id+BUFFER_LEN);
533. if(start_cache_id<0)
534. return false;
535. }else{
536. return false;
537. }
538. }else{
539. valued=caches[cur_cache_id];
540. }
541. return true;
542. }
543. else
544. {
545. return no_cache_inc();
546. }
547. }
549. void tree_iterator::clear_child()
550. {
551. tree_iterator *child=first_child;
552. while(child!=NULL)
553. {
554. first_child=child->next_sibling;
555. delete child;
556. child=first_child;
557. }
558. first_child=NULL;
559. }
561. tree_iterator::tree_iterator(int n,int d[MAX_NUM],int prod):spliter(n)
562. {
563. next_sibling=NULL;
564. first_child=NULL;
565. get_prod=prod;
566. cached=(n<=CACHE_LIMIT)&&(n>=3);
567. finished_cached=0;
568. current_child_iterator=NULL;
569. memcpy(data,d,sizeof(data));
570. build_tree();
571. }
573. void tree_iterator::set_values()
574. {
575. int i;
576. if(get_prod)
577. valued=1;
578. else
579. valued=0;
580. tree_iterator *child=first_child;
581. for(i=0;i<spliter.get_sub_group_count();++i)
582. {
583. if(pattern&(1<<i))
584. {
585. if(get_prod)
586. valued*=child->valued;
587. else
588. valued+=child->valued;
589. }
590. else
591. {
592. if(get_prod)
593. #ifdef SMALL_SEARCH
594. valued*=child->valued;
595. #else
596. valued/=child->valued;
597. #endif
598. else
599. valued-=child->valued;
600. }
601. #ifdef ALL_VALUES
602. if(IS_INTEGER(valued)){
603. int x=INTEGER(valued);
604. if(x<MAX_BUF_SIZE){
605. visited[x]=true;
606. if(x==cur_scan)
607. {
608. while(cur_scan<MAX_BUF_SIZE&&visited[cur_scan])
609. cur_scan++;
610. cerr<<"Searching for "<<cur_scan<<" now"<<endl;
611. }
612. }
613. }
614. #endif
615. child=child->next_sibling;
616. }
617. if(get_prod&&valued==number(0)||!IS_VALID(valued))
618. {
619. pattern=((1<<size())-1);
620. }
621. }
623. void tree_iterator::no_cache_build_tree()
624. {
625. int i;
626. int catche[MAX_NUM];
627. int prev=-1;
628. int m=0,sg,j,t;
629. clear_child();
630. if(size()==1)
631. {
632. valued=data[0];
633. pattern=1;
634. return;
635. }
636. for(i=0;i<spliter.get_sub_group_count();++i)
637. {
638. if(spliter.split_size(i)!=prev)
639. {
640. m++;
641. sg=0;
642. }
643. else
644. sg++;
645. t=m*256+sg;
646. int k;
647. for(k=0,j=0;j<spliter.size();++j)
648. {
649. if(spliter.get_group_id(j)==t){
650. catche[k++]=data[j];
651. }
652. }
653. tree_iterator *child=new tree_iterator(k,catche,!get_prod);
654. child->next_sibling=first_child;
655. first_child=child;
656. current_child_iterator=child;
657. prev=spliter.split_size(i);
658. }
659. pattern=1;
660. set_values();
661. }
663. void tree_iterator::read_cache_file(int offset)
664. {
665. char fName[40];
666. int mask=0;
667. int i,j;
668. for(i=0;i<spliter.size();i++){
669. mask|=1<<(data[i]-1);
670. }
671. sprintf(fName,"data\\%c%d",get_prod?'m':'a',mask);
672. FILE *fHandle = fopen(fName,"rb");
673. if(fHandle==NULL){
674. fprintf(stderr,"Cannot open cache file %s\n",fName);
675. exit(-1);
676. }
677. fseek(fHandle,offset*sizeof(number),SEEK_SET);
678. start_cache_id=offset;
679. int read_size=fread(buffer,sizeof(number),BUFFER_LEN,fHandle);
680. if(read_size>0){
681. caches.clear();
682. for(i=0;i<read_size;i++){
683. caches.push_back(buffer[i]);
684. }
685. start_cache_id=offset;
686. cur_cache_id=0;
687. valued=buffer[0];
688. }else{
689. start_cache_id=cur_cache_id=-1;
690. }
691. fclose(fHandle);
692. }
694. void tree_iterator::create_cache_file()
695. {
696. char fName[40];
697. int mask=0;
698. int i,j;
699. for(i=0;i<spliter.size();i++){
700. mask|=1<<(data[i]-1);
701. }
702. sprintf(fName,"data\\%c%d",get_prod?'m':'a',mask);
703. FILE *fHandle = fopen(fName,"rb");
704. if(fHandle!=NULL){
705. fclose(fHandle);
706. return;
707. }
708. set<number> ncaches;
709. do
710. {
711. if(IS_VALID(valued))
712. ncaches.insert(valued);
713. }while(no_cache_inc());
714. int size=ncaches.size();
715. if(size==0)return;
716. fHandle=fopen(fName,"wb");
717. if(fHandle==NULL){
718. fprintf(stderr,"Cannot create file %s\n",fName);
719. exit(-1);
720. }
721. set<number>::iterator it;
722. i=0,j=0;
723. for(it=ncaches.begin();it!=ncaches.end();++it){
724. buffer[j]=*it;
725. i++,j++;
726. if(j==BUFFER_LEN){
727. j=0;
728. fwrite(buffer,sizeof(number)*BUFFER_LEN,1,fHandle);
729. }
730. }
731. if(j!=0){
732. fwrite(buffer,sizeof(number)*j,1,fHandle);
733. }
734. fclose(fHandle);
735. }
737. void tree_iterator::build_tree()
738. {
739. if(!cached){
740. no_cache_build_tree();
741. }else{
742. no_cache_build_tree();
743. if(size()>1){
744. create_cache_file();
745. finished_cached=1;
746. read_cache_file(0);
747. }
748. }
749. }
751. int main()
752. {
753. int a[11]={1,2,3,4,5,6,7,8,9,10,11};
754. longlong count=0;
755. time_t starttime=time(NULL);
756. {
757. tree_iterator it(SEARCH_VALUE,a,1);
758. do
759. {
760. if(IS_INTEGER(it.get_value())){
761. int value=INTEGER(it.get_value());
762. if(value<0)value=-value;
763. #ifdef DISPLAY_NEW_VISIT
764. if(value<MAX_BUF_SIZE&&!visited[value]){
765. cout<<value<<'='<<it.expression()<<endl;
766. }
767. #endif
768. visited[value]=true;
769. if(value==cur_scan)
770. {
771. while(cur_scan<MAX_BUF_SIZE&&visited[cur_scan])
772. cur_scan++;
773. cerr<<"Searching for "<<cur_scan<<" now"<<endl;
774. cerr<<'\t'<<"Time cost "<<time(NULL)-starttime;
775. cerr<<','<<"searched expressions:"<<count+1<<endl;
776. }
777. }
778. count++;
779. }while(it.inc());
780. }
781. {
782. tree_iterator it(SEARCH_VALUE,a,0);
783. do
784. {
785. if(IS_INTEGER(it.get_value())){
786. int value=INTEGER(it.get_value());
787. if(value<0)
788. value=-value;
789. #ifdef DISPLAY_NEW_VISIT
790. if(value<MAX_BUF_SIZE&&!visited[value]){
791. cerr<<value<<'='<<it.expression()<<endl;
792. }
793. #endif
794. visited[value]=true;
795. if(value==cur_scan)
796. {
797. while(cur_scan<MAX_BUF_SIZE&&visited[cur_scan])
798. cur_scan++;
799. cerr<<"Searching for "<<cur_scan<<" now"<<endl;
800. cerr<<'\t'<<"Time cost "<<time(NULL)-starttime;
801. cerr<<','<<"searched expressions:"<<count<<endl;
802. }
803. }
804. count++;
805. }while(it.inc());
806. }
807. cerr<<"Total expressions searched:"<<count<<endl;
808. cerr<<"Total time cost "<<time(NULL)-starttime<<endl;
809. cout<<"The first integer not reached is "<<cur_scan<<endl;
810. return 0;
811. }

复制代码

无心人

和你上次发的有什么区别？

无心人

好像递增极端迅速 9的和10的应该至少差9*10倍

无心人

我的程序精简了输出 7的共413M输出 相当于51609600个表达式 估计8在2.3G 9在166.5G 所以似乎还是不好做

mathe

原帖由 无心人 于 2008-10-3 14:34 发表 和你上次发的有什么区别？

保存了部分中间结果到文件

无心人

0 我想，这个问题后面的是前面的规模的n(n-1)倍 所以11的需要10的110倍运行时间