TA的每日心情 | 奋斗 2015-9-17 00:58 |
---|
签到天数: 1 天 [LV.1]初来乍到
|
以下是引用游侠无极限在2004-5-2 14:41:26的发言:9 d: ~& |" I6 b! O0 w
#include . c$ @5 V% p- u5 P4 v- }9 X& t
#include
5 X" `' i1 G- f1 |1 [& w) S
6 s$ H. u4 O+ Q9 ]( B# [ int EnumFormula(int min,int max,int num,int sum);" b' l+ j& N4 J- B S
void ShowFormula(int *Num,int *Sym,int count,int sum);+ D' B2 b6 i# u7 z) g! @$ k
double GetFormulaVal(int *Num,int *Sym,int count);
& @: x8 M: M" c1 y _$ B2 A+ w; e int EnumArray(int *Num,int min,int max,int count);
3 v" A7 e0 P# _7 D0 G3 g void InitArray(int *Num,int min,int max,int count);
3 g* k. [. R9 S. R6 l const char cSym[5] = {0,'+','-','*','/'};9 S# e8 B/ D/ ~) Y
$ \8 o: m$ ^2 ?: P' L! W int main(int argc, char *argv[])$ B$ p$ X! d. q$ E
{0 m/ }% P9 Q5 Q: A- `
printf("总计%d个式子\n",EnumFormula(1,10,4,24));. j! c, x9 Y5 U/ z/ C
system("AUSE"); " }5 I6 y9 V* m& U9 \
return 0;% |; x0 ]& a& Z( x* m+ A
}
& {1 i$ W; P% U! e! \- d' I0 i* a! t, \8 I
int EnumFormula(int min,int max,int num,int sum)7 G7 h* s& l$ q% r- U- `( z' f( p
{7 |: q2 `- e5 r8 J
int *FormulaNum = (int*)calloc(num,sizeof(int)); //储存操作数
% s) H. y" d9 B! Q; W //储存操作符号7 f l9 ^$ X3 a: R" r
//最后一位用于穷举结束标记0 m* `9 g$ P& n9 D3 ~
// 1 - 4 代表 '+' '-' '*' '/', [5 u# b, n% j, X: G8 g2 B, a
int *FormulaSym = (int*)calloc(num,sizeof(int));3 W! S+ B g6 c l* ]
9 D) i- D$ N1 g5 P6 m' [2 T5 N
int result = 0;8 O) Q) j" u2 L
// 初始化操作数和操作符号数组" K3 q$ j, [. H: J
& N2 l: J1 v+ p/ N5 F. x1 R int i;
' t+ D3 K; ^! z4 h+ v1 ]: A4 U9 t# T
for(i=0;i = min;
! F& b5 {$ M, H2 Z: V# o for(i=0;i = 1; S3 |* E* E% A- z; V- C% t
FormulaNum[0]--;
1 n" s0 z6 \0 C; e4 q8 J
' B$ S2 [" z% c7 w! h8 o InitArray(FormulaNum,min,max,num);
, h" L( F! n3 e" |, C FormulaNum[num-1]++;( U1 @: J0 u6 R s% C a; x, A
// 穷举操作数和操作符号组合
( S6 S; Q' n5 V% E& \: o4 D6 ^$ h while(FormulaSym[num-1] == 1)/ J: u) A2 U5 v5 {( {: r
{
8 K9 u8 l* A1 B$ y# i) e double t = GetFormulaVal(FormulaNum,FormulaSym,num) - sum;8 {+ O% u8 A6 Y' W( N% I% f& T" t! I
if(t>-0.01 && t<0.01)3 o+ O- B: B2 Z0 @
{
$ P! S: V7 ]+ W- \2 u b //printf("%d %d %d %d | %d %d %d ",FormulaNum[0],FormulaNum[1],
* G/ p6 D: I+ @ //FormulaNum[2],FormulaNum[3],
/ p" |# ~0 }2 i2 H5 G // FormulaSym[0],FormulaSym[1],
- C' m! `$ H- x1 `1 x& X0 e. i8 U // FormulaSym[2],FormulaSym[3]);! t$ Y* A: U$ @% P" `6 E
ShowFormula(FormulaNum,FormulaSym,num,sum);
( ]; d0 |% C( S% v& C result++;, V: }5 t- P% k5 n5 U. L
}# c) i. ~* d4 ~( @$ O6 h. b6 N
4 O4 e$ h& ^ n, I x7 F1 A* i
// 依次穷举操作数+ H" e d0 P2 _: c. Y( {
. B! u. z. Q" C3 \7 U6 o //允许数字重复的穷举5 i3 }0 z( q% {+ l$ @* X
//FormulaNum[0]++;( C$ o# C- ^% w3 B. S
//for(i=0;FormulaNum > max && i
5 ~5 {, T; N0 H6 V6 g( O //{
2 X; O' p. e1 @; D // FormulaNum = min;9 j( [& f# u$ n2 K+ {. l" z
// FormulaNum[i+1]++;
* f2 e \! V' t- G% L$ ]% G //}
* P/ j# t3 @! }0 u // 操作数穷举与操作符号穷举联接6 r" Y* U- M* _; f( k' q+ _
//if(FormulaNum[num-1] > max)
: ]3 O6 w9 A2 r! U# G0 {" j //{
i! P6 k' n) c6 ]. K* G! V // FormulaNum[num-1] = min;% o4 n4 J6 L" ~
// FormulaSym[0]++;
7 |# G: N" h6 J* x0 Z //}+ X5 Y& f& f( y9 G
8 V3 b3 u+ Z+ |
// 不允许数字重复的穷举( w8 a+ @$ Z8 S( ]
// 数字必须从小到大的排列,防止重复
* L& N& P2 `$ j( I: B A7 ~ if((max - min)< num) exit(0); // 出错6 z+ S( c" }' \8 n
# _# c" ?7 I8 \7 E9 E
if(EnumArray(FormulaNum,min,max,num))
* L+ R6 J5 w5 z( O: s! } {
) F0 t; g4 L" w FormulaSym[0]++;
/ H& i; j; h( d: j InitArray(FormulaNum,min,max,num);
3 |( U# v( r6 S6 w8 {. Z( q5 d FormulaNum[num-1]++;
. h ]8 k% l6 R# _* ^% z; L } k M: @0 f7 @7 q
, t# H* }7 o; C- P
// 操作符号穷举
N" ?% s* X1 ~$ |) p" j for(i=0;FormulaSym > 4 && i5 [# B, ^1 L' Q {
& T9 R$ M }# _/ N/ e! j( L FormulaSym = 1;
: Z3 V7 _3 t+ L1 t& j5 s FormulaSym[i+1]++;
. D" K# H1 t/ A }
; C- X5 }5 ~/ a! v$ v$ [' Z" x" U, G/ |
! u6 J& E6 t9 [ }5 \! |! }" B2 _
//释放空间/ P1 F3 D2 u( L) c
free(FormulaNum);
0 r, j, n3 u! U9 y( O$ |& q0 Q free(FormulaSym);
7 P( \% Q* Q1 }, |, I/ |! X( Z6 U return result;
( [' G& T: d3 |6 r4 [6 t; g }: E6 u- L& G" X' ~
// 计算算式结果; }- J2 G4 v' O4 D! D5 f* E
double GetFormulaVal(int *Num,int *Sym,int count)( A) u, W# v7 T. m8 c
{
; f& v2 x- t% e int i,j;; K6 o) ], a, ]' U/ `. N0 w A
double preresult;5 v* c5 j' G8 u
preresult = Num[0];
* [8 V/ s" v/ J: p+ I; B8 k i=1;j=0;
/ U6 a+ M' C6 e4 h; T; ~0 I* V3 k while(i. p7 o8 L: ^: [8 z9 v
{2 r' R1 i0 X* l& f# \
switch(Sym[j])
7 l n$ j7 Y, Y3 w$ F) b {, T1 J- e7 {+ P2 [; x) [0 J
case 1:4 N% D6 J( B3 h5 O/ l; E+ Y
preresult += Num;
( G1 C7 ?% c* H9 W" t break;" q1 C3 u- U; p2 Z0 K0 ?1 _
case 2:+ v. i) D6 R5 Y K
preresult -= Num;* \/ w$ \: C& G
break;5 [9 k r; k: J' k8 ^+ c
case 3:& _0 a* a2 B2 F2 y! l& \1 E' Y
preresult *= Num;
6 U- X3 d; D, @& X5 t% G1 [ break;
2 Q- t% F) K/ u: n6 ?/ o5 ^ case 4:" d; B) c( B: @; p2 X. K
if(Num == 0) return -1000;
# D* B g4 P. f, o2 ~* ^; h1 | preresult /= Num;
7 s4 U" \ ~* ^3 S+ x( i3 D. _8 K break;
% _3 z3 N2 e+ C( A% e! r& y }! W9 C# a1 `) o' h7 g& }+ D
i++;j++;
% i& I/ C. g- L* A/ K' \( R, x }
& B2 W2 j! r. r1 l* ? return preresult; //进行修正
9 D) J6 a8 S7 E/ [ }
: w) z/ L2 v& M& w // 打印算式$ n3 A& f+ ]1 [
void ShowFormula(int *Num,int *Sym,int count,int sum) f, v$ l, }; m& F0 `, y# l
{( T1 ~) ~4 X8 M# C& Y( I
; Q+ e+ F' T' G- ^% {
int i,j,len;# K' z u6 X) U4 |3 x9 N% ~
char *Formula = (char*)calloc(count*4,sizeof(char));
+ v/ K# {3 T& b9 `, W% O( [3 ` char temp[10];
1 d* @9 L! @2 Y& I* O" d1 b itoa(Num[0],Formula,10);
/ T% W# w" j8 d- ^! t$ G i=1;j=0;
/ w+ o( O( c( y while(i1 F2 v7 P1 o' f3 \- {1 s# i
{
, H6 A) q' O* g8 D" [4 d itoa(Num,temp,10);7 n9 j# d# c/ [& j4 C
len = strlen(Formula);: Z" H; ]# Z2 [& M: U# r$ C6 h
switch(Sym[j])$ w8 B4 t8 y% K% ]7 b5 E; z$ u
{0 v/ a1 L$ S4 x4 B d" G! m
case 1:. n, t; E7 y0 L& S
case 2:. {' w8 L% J7 G7 g9 n8 U) |2 P$ ]
Formula[len] = cSym[Sym[j]];
- R: ^; z' K Y$ b& m; f strcat(Formula,temp);
4 h' I1 W* f! G break;
0 C( j; A# `* o) G# b+ n* F case 3:4 f- D) |1 ^" P* a
case 4:/ L8 [. w( X! }" Y% k9 |
2 M3 L* R& C; W7 t; ~7 n5 P // 如果上一个操作符号优先级低于当前的,应加上括号
0 b# d* }; Z# ?5 F. V, | if(j==0 || Sym[j-1] > 2)7 o( Q1 I9 k6 V4 y
{
, H4 O2 i1 A/ ~. t" p: e$ S$ P Formula[len] = cSym[Sym[j]];
$ _, m* U; J) i strcat(Formula,temp);
& w) ?) f% \ a! h }
" I! _0 x% L' ^; S5 E6 s else& Z% ~) ?/ Q" y' |) }# I) g P4 p
{
. P5 H, E9 R' \, Z* T, P3 k9 O int n;7 I* ?3 W" S7 S0 H0 l5 g0 K; Z
char *FormulaTemp = (char*)calloc(len+1,sizeof(char));" w8 u- F- b/ }; S
for(n=0;n# a& k/ N( o, v0 r- C# G9 ^ {3 e8 W& I. F% E8 b8 b! k' K
FormulaTemp[n] = Formula[n];6 s' [" W. O( F- I( L" l( G1 I9 Q
Formula[n] = 0;
( L0 A2 Y; {* h( R }4 T( a- K6 A% s, `- U( H
Formula[0] = '(';
: E( c. P! H: e* Y9 e9 }% g strcat(Formula,FormulaTemp);
! r4 v. z, y$ v: ^ free(FormulaTemp);
% M$ U v7 s* b0 _ Formula[len+1] =')';& E7 L! H& H5 N. J6 h
Formula[len+2] = cSym[Sym[j]];
+ c9 ~/ t a* I, V strcat(Formula,temp);/ _9 q( W7 B. d/ s5 G* f
}
& h m* O$ B) C) p9 L- ? break;% F8 f; M5 u6 b, t
}4 s/ T+ `# \/ o8 ?4 z
i++;j++;
& p3 Z3 _: Z$ V" K5 {( ] }% E! Y& f: Q) d) w
printf("%s",Formula);4 @3 h x( a- O. J* S, w
printf("=%d\n",sum);0 i+ `1 E6 K6 d. V$ ~
free(Formula);
0 g2 l% A% S U+ {2 ` }1 t# ^0 L( S( m4 H. @! s& ~) [; ]
0 P; i5 k7 y- Z+ e0 E: z" i( }* J Z
// 以当前数组为基础得到一个从小到大排列的数组
1 c0 ^, N/ r& C% ?3 @/ u, x4 h // 返回非0表示穷举结束
. j" F. T. V2 O$ A! H$ @ int EnumArray(int *Num,int min,int max,int count)* b6 V9 C9 k' H' F# Y6 A4 j; T$ Y
{
3 l: B2 t/ Y& O) E int i,top;
. {. h$ s: m# ^5 T( x' u top = count-1;. Z- g* N4 H5 q& S: E
Num[top]++;
8 Q3 L9 ]+ s6 M' U, Q while(Num[top]>max-count+top+1 && top>=0)& X- {6 c' Q6 B$ i/ {0 D, C
{
x* i% t. \( u- W& R top--;: N7 H }2 n' c0 Q: I0 S
Num[top]++;
; `3 W% s, A3 B9 { }0 D) l/ R8 o* r7 \! I% \
for(i=top+1;i! I% @9 j$ W) q+ ], O
{
; c+ I# `2 z& E2 t Num = Num[i-1]+1;
2 X* N _( p: o }
% N; u, Y5 `; F if(Num[count-1] > max) return 1;& R k: G) C, m
else return 0;
4 I" a3 m) [$ a/ V8 I, K; z% n( K }: ~) q" \* [; [) M& i: s5 r
; N; W7 z0 q; U# c! j U7 n/ z2 d" F // 不允许重复的初始化数组
. g) n! J5 g" ^# S" u3 J( S; X void InitArray(int *Num,int min,int max,int count)
, a! f% \5 J( M {' u; N: b. M- ^- @ L3 e. ~" e
int i;2 A! I* P1 M0 W3 u7 m; X0 a, M
for(i=0;i=min+i;# a2 l5 g5 e, l
Num[count-1]--;
* N5 g" B7 S7 X1 B: k; ^! j }: A7 a6 z+ _8 P- C/ _# c* G
- n, L% I4 E! l/ u% t . R: z. E. I7 E& E! e* u
a. z# N, g* L' B
- d1 r1 u# Q' ?9 Z H1 y5 ]3 K! u# o [此贴子已经被作者于2004-5-2 14:50:47编辑过]
0 ?4 [4 M4 \# m. `6 ]3 {9 ~
8 U u# P4 I) |1 b& Cprintf("总计%d个式子\n",EnumFormula(1,10,4,24)); 的运行结果是:
# V2 T$ F2 [6 o) B) {1+4+9+10=24
/ ~- T2 p4 |$ _! u+ p9 v9 @1+5+8+10=240 ^$ v/ K. @# s8 [/ n
1+6+7+10=24
% f0 ~- {0 \1 O. m. Y8 ^1+6+8+9=24
3 n: n/ ~! Q" Q2+3+9+10=24
; \" J6 t! }% C8 P! Q2+4+8+10=244 l( @* J8 Q' ~- w; F
2+5+7+10=247 l0 K# [# | F* F% L* s9 ?" s5 m
2+5+8+9=24
/ w! C8 q2 I/ y7 [3 l4 y1 ]. e" `+ f2+6+7+9=24( Q4 u9 E" t1 f2 A& f
3+4+7+10=24
# |( i. h$ O' m0 _2 S V1 i/ z3+4+8+9=249 Z% ], y5 R/ |: T8 v6 J% Z4 \
3+5+6+10=24
* k b" B3 m' t# X$ c3 @+ Q3+5+7+9=24 P3 P/ X) ^) |7 X
3+6+7+8=24
( ?) S. D2 j6 m! s( r8 |4+5+6+9=24
) _* f/ H/ t+ u% t4+5+7+8=24; P( D. N3 Z* N& o; S
这是什么意思?似乎是找出了 1 至 10 之间的和是24 的数据,这和完成计算24点,差很多吧?
: l. M. ?% c5 r w( O8 k比如用户输入 2 ,5,7,8 程序应该能得到计算这四个数据得到24的表达式才行啊,这样就可以写一个游戏了。+ _; t5 q g5 L# i+ x- D
如: 1,5,7,8 有如下方法可以算出 24( e: J3 J# L( ]0 G: r
((1+7)-5)*8 = 24
, I; F5 g% X' E5 A0 p' P. R((7+1)-5)*8 = 24; N1 q) H/ m7 m4 q4 @! i* w( ~5 n+ J
(1+7)*(8-5) = 24
7 z: S7 P* Z% f(7+1)*(8-5) = 24
. @# E0 r$ Y) A/ r# k((1-5)+7)*8 = 24
1 @: O- I6 p) i3 X# t( v. x((7-5)+1)*8 = 24
( O% ~3 C- k, G6 ` A. ]% R( ` h+ g(8-5)*(1+7) = 24
) a6 i) R1 I% B4 g; E2 J(8-5)*(7+1) = 24
$ L4 d& Z. C3 D5 r2 D1 {) t& k8*(1+7-5) = 24
4 b* |$ | B4 K `5 n8*((1+7)-5) = 24
* t* m3 N# C: _ {9 _% q' n/ y8*(1+(7-5)) = 24
7 G9 p. K( S1 y% v5 G. ~2 |8*(7+1-5) = 242 \* V4 A+ P4 ?: ?& w
8*((7+1)-5) = 24
% c" T2 \! b9 `& m' L+ j1 e4 b3 R8*(7+(1-5)) = 249 `1 a* Y! ^1 g4 P& _
8*(1-5+7) = 24- X f2 w: X0 c3 T* m1 a
8*((1-5)+7) = 24
7 F, s; x. a* ^; q$ k# |8*(7-5+1) = 24
9 _. _7 |2 c6 t( [% d3 r8*((7-5)+1) = 240 R" d) B, r0 s: ]/ {
|
|