TA的每日心情 | 奋斗 2015-9-17 00:58 |
---|
签到天数: 1 天 [LV.1]初来乍到
|
以下是引用游侠无极限在2004-5-2 14:41:26的发言:+ F3 o: Q( `: C2 X4 F0 B
#include
& f9 O y. z& v% f7 q% `$ r #include
8 Z) I* W- o' e7 r% n! V$ L0 Y3 @/ w& R R! D6 k' }3 }
int EnumFormula(int min,int max,int num,int sum);
: X; z5 [9 G# o7 a, I3 T* R void ShowFormula(int *Num,int *Sym,int count,int sum);/ L& o# s3 O I( N# Q& k
double GetFormulaVal(int *Num,int *Sym,int count);- k5 [) Z- I0 j! h! r8 d$ I. T
int EnumArray(int *Num,int min,int max,int count);3 X3 A2 w' n4 n% e9 Z
void InitArray(int *Num,int min,int max,int count);
9 L% b3 S+ Y9 C% d5 {/ @ e. ? const char cSym[5] = {0,'+','-','*','/'};5 w9 Z1 ?5 E2 S" e; C
5 h, Q& t* \7 T4 o6 Z# h
int main(int argc, char *argv[])) J" w" Z9 W& r7 \+ C: H+ K
{2 ?6 l5 c+ J* A; [' ^, k, |; ]' I
printf("总计%d个式子\n",EnumFormula(1,10,4,24));
5 U" D% s0 C9 u system("AUSE"); ( z/ z) Z0 G1 H
return 0;
+ C0 q7 [+ _4 R2 j }
! j8 w8 f0 a0 i/ w; h( T4 X7 L$ p8 f H
int EnumFormula(int min,int max,int num,int sum)* x' {( R+ {$ r. E
{
% P3 P9 U# E6 a; R6 X) T0 I" Z int *FormulaNum = (int*)calloc(num,sizeof(int)); //储存操作数
; {; C, @ {3 |' x //储存操作符号9 t& G8 M. H' r
//最后一位用于穷举结束标记: x6 n; T9 Z' x) J4 s W, ]# Z
// 1 - 4 代表 '+' '-' '*' '/', J H6 S1 Z4 n, t1 F* R8 g
int *FormulaSym = (int*)calloc(num,sizeof(int));
! h, }) I8 I, k3 o4 R/ l
$ F2 E* K h" H int result = 0;
0 f7 i" V! ]) U K. ?7 y( h // 初始化操作数和操作符号数组
2 {" c$ E0 u( P: ]5 F$ Q6 ~" t1 K
7 o9 m1 n* K. h+ G | int i;1 \( B( X# [' m" ]8 p
/ {8 N" G7 T& z: a; f& x for(i=0;i = min;2 p8 A& j) b9 y- ]& p' R
for(i=0;i = 1;8 s5 H+ V+ O" p ?9 m$ }2 h
FormulaNum[0]--;
, L( M5 G- i8 E+ S
2 E2 t% ^2 n/ } InitArray(FormulaNum,min,max,num);5 L+ y! r+ _/ O0 x% y$ j7 G
FormulaNum[num-1]++;
; y) n' Q0 }, U0 L6 d! d // 穷举操作数和操作符号组合* l, Y" y* T2 ?9 l, ]! G3 s1 N2 m' W1 w
while(FormulaSym[num-1] == 1)1 r2 s; f# L3 t3 N' q1 t# ?7 n9 M
{
8 k9 P" H, y* \ double t = GetFormulaVal(FormulaNum,FormulaSym,num) - sum;; ^4 d+ p8 O. s" Y2 z% d e, I4 U
if(t>-0.01 && t<0.01)! c5 Q. H8 U- N: `0 @" s
{, K+ Z! r$ \/ B2 f; Q: L
//printf("%d %d %d %d | %d %d %d ",FormulaNum[0],FormulaNum[1],
. ?- W, h; N9 j/ K1 s" a/ N //FormulaNum[2],FormulaNum[3],
! j0 X' Q/ ?9 F- F+ M9 I // FormulaSym[0],FormulaSym[1],) w* H' s( K8 s% i, r0 w- f
// FormulaSym[2],FormulaSym[3]);4 T4 A% c; k' v1 x( r. e3 d7 A
ShowFormula(FormulaNum,FormulaSym,num,sum);
. O1 q2 B5 Q6 Y result++;
4 F: J; e1 F5 s9 | }8 u D1 t" o" j
L. ]+ o0 `3 o5 J6 x" t // 依次穷举操作数
$ Q; S) M6 X$ t5 D- h8 k
" C4 w, \7 S; g0 x& D- r //允许数字重复的穷举
, P2 W. ^! ?: z# c5 z* Y& E3 {# D. h" D6 J //FormulaNum[0]++;: D9 F0 m x; y+ f' V, R
//for(i=0;FormulaNum > max && i' p! l T( I# E! h& v" ]# \1 @
//{# G+ |( C# I" k2 w3 b9 L
// FormulaNum = min;
! U u* t- O# _6 `/ D( B7 }6 i7 C6 o& i // FormulaNum[i+1]++;7 a' L+ g7 q5 {+ o# k2 [7 {+ r2 X
//}
2 e* s3 U1 R- h& e: M5 s // 操作数穷举与操作符号穷举联接
3 _, U2 C4 r3 v, ^: y5 M //if(FormulaNum[num-1] > max)7 U3 t' m I- S. v, U! v
//{2 K. @+ g6 c1 ^7 @
// FormulaNum[num-1] = min;
/ G+ u& p# t2 s9 A // FormulaSym[0]++;
/ R6 Z, N6 @" }( ]9 Z //}$ p! t+ i" S: m% M1 H0 _. z( u( s
( k" V1 b0 S7 D$ B+ c# x // 不允许数字重复的穷举
, C1 w' w/ ~% m2 I // 数字必须从小到大的排列,防止重复5 k3 [1 g" @2 j+ M, N( i2 F' q
if((max - min)< num) exit(0); // 出错
& |) n, @% O7 `+ f) i7 v: j) N" z1 `7 x1 O% U3 w- z
if(EnumArray(FormulaNum,min,max,num))5 X" I" p7 `3 a5 A
{
. j8 g' K9 \+ y% v# p# U6 O FormulaSym[0]++;
* x4 f) S4 f4 p+ m0 Z- h InitArray(FormulaNum,min,max,num);
1 \8 t; Q' k& n$ N% ? FormulaNum[num-1]++;! o# ^4 ]! m( u' {
}
9 a S5 S; E, F* N/ ?# B1 }$ `8 V & B4 A0 r' A3 D7 z& n' F6 `
// 操作符号穷举
) Z5 x9 l, M) u7 f: `. t for(i=0;FormulaSym > 4 && i/ X. w% E0 y0 ?6 \) G {4 E. z6 t3 y3 h" T6 I% L! [
FormulaSym = 1;) t4 i& v. w! P! X$ d' H
FormulaSym[i+1]++;
% g7 |, H o/ l: A4 c }( ?1 }0 y X( Q( Y2 I+ C7 [* |/ Q5 L
) y! x" O5 ^9 `- L) b6 u# w; E7 W }0 c! n, S0 {' \* |& O6 ^ h) `5 z2 _
//释放空间1 j, w6 B, q h- M( S, C" W% A
free(FormulaNum);2 f) V/ e5 G5 E
free(FormulaSym);4 f) H+ M: W. r' \- m) \
return result;. G/ ^/ F, P6 w7 Z# q3 Q+ G
}
3 V0 j3 }% e @* p' d; T // 计算算式结果
! |( f0 u+ P% M8 n% p0 V double GetFormulaVal(int *Num,int *Sym,int count)
/ ~; o- s) e* M) v- H8 R {; u! k! A: K/ F# a2 X; b
int i,j;( p0 G. z) Z1 `5 S; |& M) v
double preresult;
. q3 ^* g! e7 ]6 a! N2 k preresult = Num[0];- U9 }. d2 k; b. q$ l% Z
i=1;j=0;' y8 T3 E- P' X/ a
while(i7 J; U& }1 y+ w- C6 J
{
1 p. P& F# h5 K! x3 L. l; `8 B switch(Sym[j])! T* k- @0 }' a
{0 m9 e3 b9 \ C
case 1:5 a; ? `5 R0 M
preresult += Num;/ d# ~5 l& b* ~# \; [8 R
break;
1 k& N/ ~* K1 w# }8 ^0 v1 y case 2:
; b+ b" ]) L8 X) C preresult -= Num;
6 ]% F2 `0 r% L6 D5 y2 Y break;
$ x3 q9 D7 L' R- i# c case 3:
3 }, R6 m4 Z4 |% }: s preresult *= Num;# w9 M/ W% ^1 h
break; ]; [( f4 Z$ u) d R' u
case 4:: j- j. S5 e* T6 b/ W: W3 ?
if(Num == 0) return -1000;
+ t8 M6 L" V, W" t preresult /= Num;
2 V0 w# E8 a% h! T break;
9 t: `3 d8 [( N3 L8 U }
4 @. b! v; }8 ]8 R4 _ i++;j++;
5 C/ L/ V/ |1 Q! x# `, K }
9 U& Z; o& Y3 f$ W return preresult; //进行修正
, }8 P" [0 ]( P }& w7 M- {$ H+ R) M& {+ a
// 打印算式
4 b o g( j: s& F7 h T void ShowFormula(int *Num,int *Sym,int count,int sum)
3 G" Z& w$ S9 \# P3 u s; W3 Z {# [# j, h, z: n7 J4 F' d% O0 X
: z* S5 J2 l+ r
int i,j,len;$ u% {3 V$ [8 M- P; ^
char *Formula = (char*)calloc(count*4,sizeof(char));4 T5 q0 H" c" w/ i! f
char temp[10];
& v% t4 ]2 p9 N6 ? itoa(Num[0],Formula,10);
! w0 R( b3 A7 ~, A) `0 F* I+ i& \/ W i=1;j=0;9 d* K7 e, y( s" v! x7 o
while(i1 `- d9 G7 v* e- q) K% R. _* t2 a {& D1 G% d; ]+ k1 P8 ~- L
itoa(Num,temp,10);+ W* I: z! K. b" N
len = strlen(Formula);
* I4 K, H+ r4 O: J4 i' m switch(Sym[j])
. ~) q) t6 M" u+ `4 B B6 ^ {$ H* k+ B5 k0 N( K& d
case 1:
; A) V( y. w; c4 K4 U case 2:3 J G8 g0 }; ~1 Y/ a
Formula[len] = cSym[Sym[j]];
9 R3 F* I- }; q' \ strcat(Formula,temp);
; V' p1 ^) Y+ }9 X" z break;
2 W8 [, V3 Y0 b7 D4 F3 P: i case 3:" H7 j+ i1 m% h8 N' ?
case 4:2 R' k0 ~9 |) v2 P9 A
" s- }- B/ a9 g6 Z
// 如果上一个操作符号优先级低于当前的,应加上括号
) i7 O# Y& M* i _: c if(j==0 || Sym[j-1] > 2)3 k( b ]) F7 Q4 G4 J5 f
{
7 d+ f9 U ]! e" u7 ]" D Formula[len] = cSym[Sym[j]];! H9 V' C( X. p6 o" I1 E& H, S
strcat(Formula,temp);
6 W: o6 U: b' a S$ f }: z9 U* P. E: @, y2 }# s% v
else
2 M0 O0 B! g* |; b& N) Z, W: u {
8 x) X6 u& t- i) N1 @ int n;, r# f3 H5 n1 N8 j' B1 i9 \0 g* S
char *FormulaTemp = (char*)calloc(len+1,sizeof(char));
6 Q* H' J G! r# G" T% ?: t2 F for(n=0;n4 h. o' Z0 `9 ]8 H
{
! |4 N5 ^/ B5 J& m7 u; K' ]6 t FormulaTemp[n] = Formula[n];
) x8 v: Q0 V S, B Formula[n] = 0;& U! f: ^) B8 u+ M
}
& o8 f6 g k7 c% y# m k0 j& s Formula[0] = '(';
! u' l' t2 N# i- ]: R8 T5 C- r strcat(Formula,FormulaTemp);
0 H' q9 E F/ l9 S9 q free(FormulaTemp);
; S$ `: J: v& p, W Formula[len+1] =')';
3 K: `1 \3 d6 l/ E& `1 O5 {9 g( e Formula[len+2] = cSym[Sym[j]];6 J' W$ W% U5 _# G
strcat(Formula,temp);# j5 u2 e) c0 V: _! O$ Z( d
}
2 R, p6 Y+ N$ U7 \; D break;0 a! M E! h1 B; i- r0 v
}! I5 y+ v+ p% {0 x: l
i++;j++;# m& _/ k. Q: ]2 U
}6 D. M' V6 v5 Z3 o' V4 G1 i
printf("%s",Formula);% V. k& c5 ?: p. \ E
printf("=%d\n",sum);- I, A8 q3 h2 U, g/ S$ e" k
free(Formula);
* ?8 |+ ]+ V2 F* p5 z: F! @ }
! s) f( l Q& w" z9 M
0 i0 H, N+ G7 R. j7 w6 d // 以当前数组为基础得到一个从小到大排列的数组
c+ _2 U' o: B3 Y5 U // 返回非0表示穷举结束
! f0 @: l0 s7 w, o# t int EnumArray(int *Num,int min,int max,int count)
" H% U0 W8 V( h, Y+ U8 L {
. o/ E5 |8 w- U z) F int i,top;5 x- ] u: n' H# }9 O( |
top = count-1;. M6 O$ Q4 O; \- e
Num[top]++;1 U% U" n/ @! m5 ^* X& D/ E, |
while(Num[top]>max-count+top+1 && top>=0)
/ w$ M9 b6 }1 F7 l {
1 l5 J6 f8 F7 H# O4 y top--;% W. L% i- ~6 |9 w/ e. U* p# R4 }% O7 C6 @
Num[top]++;- ~8 c8 i, ~* r: @7 I7 d
}" o& y7 J6 N& I/ n/ i
for(i=top+1;i' W; P! Q; h! Y) c# G
{, G! @3 Y0 U1 N' q7 T" h, D
Num = Num[i-1]+1;: E/ s4 [; E" ^/ ~- u
}5 N% R/ {8 M& k! g( J7 A
if(Num[count-1] > max) return 1;7 \! M% l6 w: W) Z
else return 0;6 U5 w( t" k/ g# I0 ?0 ?
}
% A9 _5 e1 w1 d: O" p
1 V, y- @( ^5 | @- i // 不允许重复的初始化数组
3 y- i' r' Q7 v# h# S6 j void InitArray(int *Num,int min,int max,int count)5 R. j% f0 o4 _1 o5 Q. |9 U2 c
{, Y9 G" p3 Z- D: }
int i;
) z; L, C) `1 z | for(i=0;i=min+i;
4 x$ C! u, R) ~ L7 T- l Num[count-1]--;9 {& W; R5 B; ^4 P: ]$ z0 L
}
* W* R5 X! a4 A' H" W) g9 K# a+ ^4 S; `7 S# R
) b& J$ v8 M( m8 {, q( w
) s- p. v9 r% B8 a; t5 A/ j ) o- ^0 L. O$ Y+ |+ G
[此贴子已经被作者于2004-5-2 14:50:47编辑过] " @' ^/ E$ t7 E
6 v5 `" U, L: v4 W' }
printf("总计%d个式子\n",EnumFormula(1,10,4,24)); 的运行结果是:. p8 l- L ~! Q/ |( Z2 J
1+4+9+10=24* b" {- }/ z0 l6 |. u
1+5+8+10=24
9 M( s9 Q! G7 [1+6+7+10=244 q3 p0 u& j6 H" n, Z4 ?! ]- [
1+6+8+9=244 k; p' S6 `: Z& d; D; Q
2+3+9+10=24
) w0 ^+ Z6 {6 o* G2+4+8+10=24% M; y/ P! N0 [% z1 w
2+5+7+10=24
8 B [8 e3 Y" f# \2+5+8+9=24
$ j4 h. F" ?* g% l2+6+7+9=245 S- |4 d* p5 ~6 r) l O6 ^4 c: Z
3+4+7+10=24
! \* X- S$ H" I( H3+4+8+9=24
3 y, n# v4 C% u9 T9 x) S$ x7 A5 I3+5+6+10=24+ \8 s% \* H* r* ~ E) Z
3+5+7+9=24$ l3 x) |+ K) s, u$ w; J: @$ T& d
3+6+7+8=24. g. i, M5 L6 p
4+5+6+9=24
! t$ c4 q( ]* s* v& G1 p4+5+7+8=24) i$ L( X) S2 M+ r/ K- A% x+ |
这是什么意思?似乎是找出了 1 至 10 之间的和是24 的数据,这和完成计算24点,差很多吧?
5 }( B+ X0 D/ c6 X4 b+ ]比如用户输入 2 ,5,7,8 程序应该能得到计算这四个数据得到24的表达式才行啊,这样就可以写一个游戏了。4 a7 t2 O6 e/ f
如: 1,5,7,8 有如下方法可以算出 24
" m: e4 y, S: Y" V# s% W((1+7)-5)*8 = 24# A( j* x1 E# _1 U" n3 }
((7+1)-5)*8 = 24' E8 @: f0 W3 n) Y
(1+7)*(8-5) = 24
# _/ ` D; c4 c(7+1)*(8-5) = 24
8 L7 _% I1 g' h1 H0 K3 S9 y0 e((1-5)+7)*8 = 244 l! B* F0 Z8 `/ \
((7-5)+1)*8 = 243 ^4 L2 D7 w) x0 ~4 D
(8-5)*(1+7) = 24
; x+ ?" h/ m" B* @(8-5)*(7+1) = 24
) F- @5 G1 g4 } O" w8*(1+7-5) = 24. n# ?& e" o& {
8*((1+7)-5) = 24- l# i) x% |6 L
8*(1+(7-5)) = 24
1 r) R7 e0 p4 Z# z3 I8*(7+1-5) = 242 E$ x) U1 m4 a, L) N
8*((7+1)-5) = 248 M. n5 e: d* a' K' n
8*(7+(1-5)) = 24
6 M# N3 L- l9 m; I2 V8*(1-5+7) = 24
8 m" L" @& \* r% c8*((1-5)+7) = 24
3 P0 N' D! e2 l0 Q' w8*(7-5+1) = 24
~" u6 y8 k& T# {" m/ u8*((7-5)+1) = 24 j5 n$ @+ Y+ y& |" n
|
|