TA的每日心情 | 奋斗 2015-9-17 00:58 |
---|
签到天数: 1 天 [LV.1]初来乍到
|
以下是引用游侠无极限在2004-5-2 14:41:26的发言:5 {9 w) Y0 W6 t
#include + y8 f s) G4 u- C# K
#include 6 M! x# }5 c( i c
) S& {# [# n, q! s. }" N' D# y
int EnumFormula(int min,int max,int num,int sum);
$ S. w0 x. B6 q. N, s# P void ShowFormula(int *Num,int *Sym,int count,int sum);
% @/ Q# Z0 c1 t. c: T double GetFormulaVal(int *Num,int *Sym,int count);5 _. w3 j* y& p9 y1 ]+ r
int EnumArray(int *Num,int min,int max,int count);1 q6 u0 ]- x7 b. P. f/ @+ N
void InitArray(int *Num,int min,int max,int count);/ P; B& R* U. g# d% m/ e3 u: X$ ~' M
const char cSym[5] = {0,'+','-','*','/'};. I2 Z9 q$ `4 a
# t d* ]+ s8 }2 w9 N* i int main(int argc, char *argv[])
# I+ N, }( Q: N" Q* ~4 o {
0 ~: w8 p- M( q! g1 I* \6 e printf("总计%d个式子\n",EnumFormula(1,10,4,24));
: q1 o) U+ l3 O* c( r4 f system("AUSE");
& v; F+ ]9 _* e. Z! @ return 0;
& X2 h) j! S C' T# R! S }/ C1 s, U- ?" o) T/ b
1 a! O2 }: Q4 B4 i2 c int EnumFormula(int min,int max,int num,int sum)( H/ h( V1 D( [
{
& Q: v! @& A/ i int *FormulaNum = (int*)calloc(num,sizeof(int)); //储存操作数. ]4 B* ?, h0 X+ t
//储存操作符号
! C& F/ V) y+ ^& |0 Z% p //最后一位用于穷举结束标记
+ K( @$ ~5 @5 x2 G9 S3 X // 1 - 4 代表 '+' '-' '*' '/'+ B& E" n$ S* m
int *FormulaSym = (int*)calloc(num,sizeof(int));, ^' v' F x* V& z- `8 k G
9 L6 N5 x6 m- a& u0 I7 e& f int result = 0;
+ I1 c! Q1 R0 f+ w( N // 初始化操作数和操作符号数组5 a4 @0 E' ^4 l/ M! M6 ]: P2 K
# y+ T( c; ] b
int i;4 e3 q) t+ z2 {3 z; z7 m
% _' Y2 w+ U, v/ _( E2 \ for(i=0;i = min;
' X& l1 @( m7 ~ for(i=0;i = 1;( c' z$ H( ^$ ]' U4 g* F
FormulaNum[0]--;0 j. ]3 s! }) e h, ~. s
# n! q9 z4 i v" o, P InitArray(FormulaNum,min,max,num);- B7 T/ S2 c4 h! d- F
FormulaNum[num-1]++;
1 x' h1 E& z1 X; e1 s // 穷举操作数和操作符号组合" T9 I! r7 j% R7 P/ `5 [! W& ]
while(FormulaSym[num-1] == 1). g, ]3 K0 N' H; g2 Q9 v+ M6 {
{
1 b# {$ ? a; J) k/ @5 P' t double t = GetFormulaVal(FormulaNum,FormulaSym,num) - sum;
0 R! I: Q! I3 _+ i/ a if(t>-0.01 && t<0.01)
- X* t. |8 d V {
5 u% A8 t! ^- g( J. u! e- W //printf("%d %d %d %d | %d %d %d ",FormulaNum[0],FormulaNum[1],
" } g/ A% \* X //FormulaNum[2],FormulaNum[3],
& P R$ `7 L! Q1 k- K9 X% m( B9 o // FormulaSym[0],FormulaSym[1],
0 N! E w4 l- I3 `7 {9 {; s // FormulaSym[2],FormulaSym[3]);
" a" C6 l( X! A* R/ q) j ShowFormula(FormulaNum,FormulaSym,num,sum);
. m$ x0 _2 Y( e3 `$ p, a$ `! C$ C result++;0 Y1 ]# {. y5 U( {8 i2 C0 Q/ w
}, f/ y' p5 _/ K
* L) L& S8 T' `5 |3 U1 |5 o // 依次穷举操作数
6 D) b" A3 K; G) } 3 B. G4 s$ c8 p; ]) ^
//允许数字重复的穷举5 f! P6 ?! Y3 o& V3 ~. P
//FormulaNum[0]++;) R8 K- v }" t) |5 n
//for(i=0;FormulaNum > max && i
k' m+ e; L. U0 F8 \) E //{8 r# q. }2 u. S2 y( i1 d
// FormulaNum = min;
/ X8 }8 c, I& u& v // FormulaNum[i+1]++;0 A; `1 M# o7 M' W! k
//}
9 n% G$ |9 B$ N; W5 z // 操作数穷举与操作符号穷举联接
+ S( ^. y2 f h/ R //if(FormulaNum[num-1] > max)+ a8 B1 H% E. q0 q6 \
//{
6 |; q Z a( f' Y // FormulaNum[num-1] = min;0 l8 B) i( Y8 t0 i4 c; B5 \3 Z
// FormulaSym[0]++;
* t! N7 v0 d, i //}# O" p5 ^' d1 V h" U8 E
2 C4 D- ?! K6 ~) I6 e6 U" n& s // 不允许数字重复的穷举
; B$ k$ {! N3 u9 R2 E8 O5 X D // 数字必须从小到大的排列,防止重复
) ~$ J- D' G1 K' ?/ [! r if((max - min)< num) exit(0); // 出错9 x! h) e1 u+ E \" E
8 |, g! p1 I9 K if(EnumArray(FormulaNum,min,max,num))
( R2 S: u4 F2 Q( X8 T {' R7 S! f- a0 A$ w2 ?9 X
FormulaSym[0]++; u1 A1 j8 l) X7 v. ^
InitArray(FormulaNum,min,max,num);5 G) I, S% U* l
FormulaNum[num-1]++;& U9 [& C% D4 c
}: }0 z2 @ l$ ]9 A! j u6 b! d
- G- ]% [( ?" p: }8 S2 c4 a# ]
// 操作符号穷举' ]! J& O7 j. w1 N, y' P# I
for(i=0;FormulaSym > 4 && i$ ^, g1 d5 j; z) o0 t7 p, u% c
{. M5 u5 D0 ?3 F) i: b, k
FormulaSym = 1;
* t* X! _, x6 j5 X% F FormulaSym[i+1]++;
$ F. A7 K# N6 I9 m' M; a; d. R }7 M# n3 Q! g* N( M5 G! U
& n* D0 F$ e2 A8 @) `' Y9 G X
}
+ W" `: @) @% c/ L //释放空间
& `6 i0 O* X% R3 n5 R) C/ S free(FormulaNum);
. K: P2 e1 J' f- J, A free(FormulaSym);
$ L0 O' c+ ~3 W- X8 Z return result;5 a1 I8 l" P) l8 Y- I+ }+ [" V
}
3 T7 g" t4 ~- W) w6 H. Q! W% Y& c // 计算算式结果
5 G, A' X) i' d1 ?3 [) x! p3 i+ Z double GetFormulaVal(int *Num,int *Sym,int count)
$ u1 N. p0 \. W, j {
' K7 P/ m- O2 C( _8 R int i,j;
7 F9 D9 G% R+ P* O M; { double preresult;) j b4 K2 \; t+ U, |5 _
preresult = Num[0];
$ @) i$ `( N: v/ I i=1;j=0; o$ T: ^7 m; o' q l
while(i s, [1 K; m0 Q& s; F, `
{
M, Z8 N5 X, ? switch(Sym[j])% N, @: j/ J+ z/ Z, c1 i# ^- |
{! s1 t# q; _ M7 t9 a5 G) Z
case 1:
; x. Q! R. U/ p; z preresult += Num;4 K" W$ U$ V9 z* x+ o. a
break;
4 T+ w/ x1 \- M* M+ u& _- \0 w case 2:
) X# ]! p3 t! ]& \ preresult -= Num;9 q4 S: g5 p- A7 Y5 c L
break;! \; N* o* X V# o t2 |$ p! w }/ C
case 3:
3 f/ K' ^( G/ K; ]5 w preresult *= Num;
5 a# ^8 K. I0 v! G( c break;4 T2 y' A% ]! g# i4 S+ }$ ~) v
case 4:
" L+ o) F0 l* _ if(Num == 0) return -1000;
! ~, K6 z a6 m% K9 \1 C preresult /= Num;
: E0 _2 y2 w* i% D; J break;
- M( Q' x3 j8 K" d2 Y, z }
: _, G* b5 t" f! |9 j- O i++;j++;0 p& ~+ N3 Z% v- c& h' d: |8 v
}
# B2 J& t3 A; x# h0 e return preresult; //进行修正1 G( P5 e1 T4 E, [5 |4 c
}
1 E- e1 E: A: @# C- o; C# J2 T // 打印算式
! U7 R5 U& ]- m* E- R+ G# |4 y- C void ShowFormula(int *Num,int *Sym,int count,int sum)
9 @$ `0 P+ L8 E+ \9 j: k. V {
6 p& \: A# h! s& g% b5 G' D0 P, v2 m3 Z. L& d' G
int i,j,len;3 g8 V; J$ S _' P' f B* X
char *Formula = (char*)calloc(count*4,sizeof(char));
# b3 a: g4 k, z8 v! Q/ T5 R# f) }! @ char temp[10];
# m7 z$ l% q: o8 K. R1 P; f2 J3 N itoa(Num[0],Formula,10);$ Q3 b/ J- q7 Z3 N# F
i=1;j=0;. [, b9 A6 H& C5 R( q( c
while(i% ~8 Y3 g$ Y, O; Y! k& [( m' M3 }
{2 a8 e3 S' j& d$ |& z
itoa(Num,temp,10);. x* K1 P8 {" r+ d# T M; P; ^
len = strlen(Formula);. o0 n& g Q8 W- E
switch(Sym[j])2 M% Q& _' l/ x$ e; j
{
: o$ d* S! v ` case 1:
' c& _) x/ x% v) W, I( j# ^3 |) `1 Y case 2:
, `: H: x% h, x9 {- O0 _5 x { Formula[len] = cSym[Sym[j]];
, f+ ?, P( C; H strcat(Formula,temp);
& ]6 q6 p! p! @- | break;, n- h* z3 h; ^- T ]8 B- I
case 3:
* Y& D% Q/ _1 T case 4:1 T3 E2 X8 |# i! O6 N' `1 i7 y
% w8 T% L4 X; V N/ c* T1 M+ ^
// 如果上一个操作符号优先级低于当前的,应加上括号/ g2 o; {* F6 R
if(j==0 || Sym[j-1] > 2)
* v6 q" M! b6 Y0 T {! }. w- {" R! T- f& W$ P
Formula[len] = cSym[Sym[j]];
" v% o& \9 j( W* D& N/ G( Q strcat(Formula,temp);9 {. L' t: c, Z# |4 E
}
. K. w! I$ B/ J/ ], G else% ]% E2 x6 ^5 \. E% l: n- @; A9 R
{
% v- \3 ~& S+ f- l7 `0 y- [( ? int n;" o, R: D/ P( F$ Q& Q; ?) m" p1 l' A
char *FormulaTemp = (char*)calloc(len+1,sizeof(char));
0 \# Y# K7 M7 p5 B# M. M% E for(n=0;n- i! O2 b4 v$ n- S4 z
{
8 n0 \- B' Z6 v% D0 c: H7 P. [% k FormulaTemp[n] = Formula[n];
0 u% J# M* k f) {3 h0 i Formula[n] = 0;9 d U. L9 D* h& e2 Q
}
: s q) O |. u8 H, k1 b: H Formula[0] = '(';2 c! N1 d& _+ y. K4 }- n3 v
strcat(Formula,FormulaTemp);+ i- a9 O# h1 s# y! V3 l
free(FormulaTemp);4 S' f% f7 ~3 A& z% {
Formula[len+1] =')';1 Q9 s, k$ X1 d' t9 J
Formula[len+2] = cSym[Sym[j]]; d. P1 P7 M2 \0 B1 k) t5 u$ ]% R5 ]
strcat(Formula,temp);" s, f1 o V% T
}
% p6 c, b+ g* c break; H1 C9 A/ w& L: B$ ~- C1 a
}
2 l& l$ L+ w3 s6 ` i++;j++;. P) M1 R& `% [" N1 R: F% W0 V; i
}
0 y; j. |* }7 j4 p9 \* l printf("%s",Formula);
( k: n' j C: m C7 u$ Y. V printf("=%d\n",sum);
; i* U; n Z o. ^ free(Formula);' Y% y$ r" z5 }" |
}
% ~1 g; R1 I; E0 M. Y" t5 |
! I) f f% }8 ^3 Y W! C+ H- m // 以当前数组为基础得到一个从小到大排列的数组
6 M4 t+ V- i- G; q2 ^0 H3 n // 返回非0表示穷举结束
" q8 D, y* {$ U$ e5 L int EnumArray(int *Num,int min,int max,int count)6 Z6 J. Q) ^! v
{ Q: m5 X) |" v) n; k; ?
int i,top;
, T' `3 ^, f% r! y top = count-1;
5 I1 ]) _- X; \3 j Num[top]++;
% Q# N. [1 V! K# ]5 [, n while(Num[top]>max-count+top+1 && top>=0)9 U. U- X/ r# l6 n( D8 E* j: q
{+ D6 t! ~" ~1 S7 k: j7 O
top--;1 q& a2 n( ]7 b/ p; V6 t+ d# c
Num[top]++;
. g( J7 P9 F, y1 j4 C3 C# q }2 W% n% f& n' _' g% g' {
for(i=top+1;i" A; _9 @! T5 x( z/ U: q3 D4 n {3 h3 `" l9 s3 n- m2 E& s- d
Num = Num[i-1]+1;
; A8 ^+ S1 `. r* ?" B- s }! b O! M4 u3 R
if(Num[count-1] > max) return 1;* W$ t5 i: d1 z4 b2 l h
else return 0;' R7 K6 \# Z% A; Q" o( X- F5 u
}( D% v! C& h$ j3 O3 {
3 p* k# J0 v1 Z) G3 X: v
// 不允许重复的初始化数组; i d8 E" ?2 m- Y! P& c* I
void InitArray(int *Num,int min,int max,int count)" K% G: E. M4 h* W' Z
{8 y: r( }+ G A; w3 [2 J# c
int i;
, S5 V' A6 b) u: C0 w for(i=0;i=min+i;
% I5 |2 u7 c0 h* I0 G: h2 r Num[count-1]--;$ ?- q0 S: z, ^3 f$ _
}! Y" M5 G. W, @6 ^7 D
4 B+ T, G- i) d! l) k. h- E
( V U9 U/ s5 }+ S2 b' z. u# |( N4 |/ m* G6 J
& w( `3 t& q% ?' `( N: E [此贴子已经被作者于2004-5-2 14:50:47编辑过]
5 ]5 m! ~( ^& U$ r/ w3 n
% j9 ?0 V) C$ |: f. E6 L, v( [printf("总计%d个式子\n",EnumFormula(1,10,4,24)); 的运行结果是:
. Q" W. Q* ^, j2 U& P8 g+ Q) r# W1+4+9+10=24; U) `4 ]& U9 M6 s# ?: s
1+5+8+10=24
9 J0 X, s9 k$ M' _1+6+7+10=24& i& j; Q( [9 ?5 o* d5 n
1+6+8+9=24% z s& w7 n! l3 w5 K
2+3+9+10=24
# L8 b8 w- Q# f: @2+4+8+10=247 X) W( g9 {& Z
2+5+7+10=24
" A. p/ v& d# v& a J5 o) g- D2+5+8+9=24# ~4 q+ F5 ~. S" t6 o: J# }
2+6+7+9=24
% |( M c# K- C3+4+7+10=24
- a% K# L2 M, z3+4+8+9=24
) k6 ]6 ]0 |5 S5 c3+5+6+10=24
- P6 u1 ^5 M0 Q8 E$ j3+5+7+9=24$ r( n& T9 R! ?
3+6+7+8=24
9 O3 D3 s2 R9 e* K* O1 I7 _0 d4+5+6+9=249 W9 _) T7 W& U% m
4+5+7+8=24
& \ X- ]) W9 \9 n! n q+ M8 k6 l这是什么意思?似乎是找出了 1 至 10 之间的和是24 的数据,这和完成计算24点,差很多吧?
, l6 Z- S" A$ E! j比如用户输入 2 ,5,7,8 程序应该能得到计算这四个数据得到24的表达式才行啊,这样就可以写一个游戏了。
8 c7 l, I: @9 F8 G如: 1,5,7,8 有如下方法可以算出 24
1 N" B& V/ Q2 {# g1 e1 L4 Q((1+7)-5)*8 = 247 D e$ s4 J1 `4 |: c+ h
((7+1)-5)*8 = 24
& Y4 i8 T9 P1 y(1+7)*(8-5) = 24* @; `8 L. n8 b1 Y
(7+1)*(8-5) = 24
* \% [8 q: ]* E( K2 T: F((1-5)+7)*8 = 24: l9 Y' {# K# c% p
((7-5)+1)*8 = 249 B. c, u, W# F" \! q# L
(8-5)*(1+7) = 24
6 O5 D h }/ ~(8-5)*(7+1) = 241 @# C' I' p# O4 i
8*(1+7-5) = 24
h' [# a" N9 k8*((1+7)-5) = 24
M# V! k/ `4 T* H; W9 f5 [+ H8*(1+(7-5)) = 24
# c0 G+ Y6 \, Z8 s6 d$ ?: `. f8*(7+1-5) = 24. v, B/ Z& W- A) A
8*((7+1)-5) = 24- q5 z/ g' w% p; a9 n+ e) z0 _6 q, V
8*(7+(1-5)) = 241 }7 `% [. |- `. d+ l4 r+ [
8*(1-5+7) = 24, M& q; V4 N: A& }, |
8*((1-5)+7) = 24
: `6 R l. u+ b5 U8*(7-5+1) = 24
; ~% D# Y9 P/ N8*((7-5)+1) = 24% f9 R7 y9 d5 `2 e+ I9 { j
|
|