TA的每日心情 | 奋斗 2015-9-17 00:58 |
---|
签到天数: 1 天 [LV.1]初来乍到
|
以下是引用游侠无极限在2004-5-2 14:41:26的发言:
f7 d. W) t; F) V* p; l/ A3 u$ W#include
8 K7 E' N+ D! C3 h #include
, w: p8 ^/ _- n. F( f; ?
" y% e+ @/ P" v int EnumFormula(int min,int max,int num,int sum);
5 U3 P3 u) T" y# F5 H% U' H void ShowFormula(int *Num,int *Sym,int count,int sum);
) w- E( M4 T' C" W double GetFormulaVal(int *Num,int *Sym,int count);" u9 l9 X1 i7 ~5 V& d
int EnumArray(int *Num,int min,int max,int count);( `" v/ E8 G0 R. s) l+ Q
void InitArray(int *Num,int min,int max,int count);
; l/ K. g- n3 F; c const char cSym[5] = {0,'+','-','*','/'};. g6 A1 Q: \3 @' e% \; m
R6 ]$ E( q6 |- H8 P2 w int main(int argc, char *argv[])
' O# ^6 a) S9 `8 D; r4 j {
! E. N% ?/ ]" ]( d& ? printf("总计%d个式子\n",EnumFormula(1,10,4,24));
. ~7 m1 g! f% \2 K4 ?+ K+ U. i* J2 e system("AUSE");
, N6 P9 Y3 [9 @1 K4 v* c return 0;3 C. g7 `' }4 h9 l: t
}4 X! K# j1 R: B W/ Z9 b% a
0 f% m4 Q3 C+ d
int EnumFormula(int min,int max,int num,int sum)) F- @: n- \1 z) \4 _
{8 j, q, q. z7 N5 n/ t
int *FormulaNum = (int*)calloc(num,sizeof(int)); //储存操作数
( j1 L9 n8 D: s" r @( B //储存操作符号
2 Y+ b3 L, D% ]- O$ q: [ //最后一位用于穷举结束标记6 j8 I7 ^+ x2 z. L+ p! w8 j
// 1 - 4 代表 '+' '-' '*' '/'1 n& v- f7 |/ Q# r2 S
int *FormulaSym = (int*)calloc(num,sizeof(int));
: p0 o0 R- |3 N
, m& T7 t: j7 o( d x) U3 s5 p int result = 0;. t/ N& n- Z' j# c8 Y5 a% x
// 初始化操作数和操作符号数组
" X& J8 X3 Y% f& I H " b7 v. j( A% {* G7 Z8 `" F8 U3 O) O! ]
int i;6 R. g' t: p; Z
# Y$ k" X) g3 s6 o7 F& i9 Y for(i=0;i = min;5 n# V8 d! F6 B1 Q
for(i=0;i = 1;4 b" W4 p% J/ c$ v
FormulaNum[0]--;
, p6 M- p# S4 V# t( g4 l8 [& N& `2 l" B' p
InitArray(FormulaNum,min,max,num); m/ Q G6 @/ {* C6 N* \3 d ^: @5 b
FormulaNum[num-1]++;' V7 E V) s' F8 J' W2 t9 r
// 穷举操作数和操作符号组合; ?4 d, V6 w2 U# e9 s# b/ z7 n! T
while(FormulaSym[num-1] == 1)% q9 d& c- b- _2 p# n
{
8 V! a, ]1 b& }! ]0 c6 L double t = GetFormulaVal(FormulaNum,FormulaSym,num) - sum;
' w4 B* X2 {' @) u) F" A$ A4 ? if(t>-0.01 && t<0.01)
1 \6 {: m5 f( n; l {4 @/ @0 ?1 \$ L3 z4 E( Z+ [* [
//printf("%d %d %d %d | %d %d %d ",FormulaNum[0],FormulaNum[1],4 m& o) ^5 i+ C$ s8 [& [ t& ?; x8 V
//FormulaNum[2],FormulaNum[3],- T0 e) o3 n' J0 m
// FormulaSym[0],FormulaSym[1],' |$ |/ F3 o* D
// FormulaSym[2],FormulaSym[3]);" Y, x" w: [+ S% s' [- \$ f2 b
ShowFormula(FormulaNum,FormulaSym,num,sum);+ h8 d8 ^# G7 J% h
result++;
" m3 s/ S* y4 a( d- w& ~ }, E& l' ^6 O, L+ h. v
: m5 u* K2 J( I% |# y2 m // 依次穷举操作数
0 V2 s1 _- T4 r8 z* F- _0 z' l8 x " ^9 y. V& v; r0 e5 T* g- m- ]
//允许数字重复的穷举
4 Q. x g6 Q1 V$ _, @3 ?% ?( z( U //FormulaNum[0]++;/ _2 C% u" D1 `
//for(i=0;FormulaNum > max && i
2 ~6 D# x: F( v, O3 Q //{
, N ~; L* k& S5 l, k; m // FormulaNum = min;
" d! v& n% G( R/ {) h // FormulaNum[i+1]++;
& y4 u# {) U; _6 F9 e3 c% ] //}* K4 C( b6 D' f7 {% m4 e8 [, s
// 操作数穷举与操作符号穷举联接8 f( x4 } S9 }: G j/ p
//if(FormulaNum[num-1] > max)
1 x9 \: b) U' Y5 p" }. K1 ]6 a //{- K; u1 \. a2 g6 S
// FormulaNum[num-1] = min;+ Y" g7 N1 _$ S& Q
// FormulaSym[0]++;4 l& a) M7 {, `* B% z+ E, v" s# B
//}$ t0 }* m+ b8 z4 @8 ]9 E
& s4 \5 i2 b6 [7 `$ F+ V // 不允许数字重复的穷举/ w3 s% m* `, m. i
// 数字必须从小到大的排列,防止重复
& [' |% u# q: L: U if((max - min)< num) exit(0); // 出错' m2 b' q% n( ?
& ^0 u4 Q/ E& z B8 Z* v+ ^
if(EnumArray(FormulaNum,min,max,num)): s8 J! |0 x4 ~ v/ f* }- C
{' `! X& a/ q9 o" G+ n) I# D( j. ?
FormulaSym[0]++;
4 _7 u! S' t' }8 K: [- \+ W8 Z InitArray(FormulaNum,min,max,num);, X! D: r4 `1 ^5 |+ s
FormulaNum[num-1]++;
# W2 I5 k, G) N; b" k }
' U5 Q% r8 s: p5 ^( I; [: a& H
8 s7 p1 t6 x5 `5 L; ]* c // 操作符号穷举
0 ^, u1 _5 j6 C/ `. ] for(i=0;FormulaSym > 4 && i2 w- n, H; _: t' ]0 r; t {
" L, h) i5 S- w; A9 t% \ FormulaSym = 1;. G& Z, ~# j7 j! n: t
FormulaSym[i+1]++;( R- |0 ?2 r% d
}1 m; X( H2 X" d# q& |7 n
% t& M# n Q( v- S' G8 I H/ z }
w+ g1 a/ O, q6 M7 k/ S# B- B( R& D //释放空间. F/ H1 ~9 }: w; z
free(FormulaNum);; c0 O- T2 O) z
free(FormulaSym);6 B5 P8 E* r, s U4 X+ b8 [
return result;5 o& A- |8 R$ e: U
}7 M, `: \# _& Q2 H! p9 g
// 计算算式结果
9 j8 ]- x; l+ P( A4 v* d `$ [ double GetFormulaVal(int *Num,int *Sym,int count)$ M$ b$ }! X9 O9 O
{
1 U0 d D1 b6 G# r" D int i,j;
, X: F) ~4 X _$ W. ^: d double preresult;) S; R8 E( `! u s; A% U, @& Y
preresult = Num[0];* p# W8 ^" w: |8 O8 m8 i3 S0 g
i=1;j=0;
: E; C7 X7 Y. m) Q, ^ while(i, A, p! g% }3 d1 ?
{: i+ e0 i* \) a. K% ]& T& V4 r
switch(Sym[j])
" q9 w0 t3 F5 K! S) _" \ {
' i0 X* l0 x/ t% A" J' l" G: f case 1:
6 P: A3 S' a- _. [ preresult += Num;
: x* m2 f9 _; X Z1 I9 U break;
% {# L% z# i. X Z case 2:2 e+ K7 u, z1 v/ j# O
preresult -= Num;
3 ~) ^! s. [/ i! a( l2 h- G break;
1 a! H% V, F( {+ a! r case 3:: |( g+ ^/ @ o" Q/ h8 s; h: T
preresult *= Num;
, \6 a" t5 b7 ^& I' j8 B7 @ break;) [8 |% [+ G% B
case 4:
0 Y8 I$ E- S9 |" B1 P* h. ~ if(Num == 0) return -1000;5 I ^; D& X& D( ], r) P
preresult /= Num;
- y$ [0 s1 R B) ~2 s3 n. m break;5 W& ?& E& _( y- b4 J1 o
}
1 F. Y" B$ m, f i++;j++;7 ?, K q' E$ k1 t2 \
}0 F u8 |4 [: [( K# s* c' |0 J9 ^
return preresult; //进行修正; u8 F* v f4 G9 i, @; `
}& @2 d, l- {8 g* d- x8 P( }# d
// 打印算式2 `- B. g4 o* O0 t; w/ r( I+ _& p
void ShowFormula(int *Num,int *Sym,int count,int sum)
) ~6 p- E4 B5 x2 {6 o {: }- T+ a# \+ |
7 `% E3 y6 \: G4 C' J2 c# F int i,j,len;8 I W- B- B/ Z2 n
char *Formula = (char*)calloc(count*4,sizeof(char));
. O6 f+ j$ [. H$ R3 E9 P8 o char temp[10];: o( D) r4 y/ Y) v
itoa(Num[0],Formula,10);+ J+ Y; [! |, `: B+ J! \
i=1;j=0;7 }/ R4 U7 L$ `% i! f) p1 e' j
while(i5 ?% Y) }% L! ^" k- V {+ u- O& z. q4 H& |
itoa(Num,temp,10);4 W# q# p: `/ w1 c& {# _
len = strlen(Formula);
# J& R. D6 m U switch(Sym[j])
" T0 \2 J r# _5 Z6 P: u) M- y {5 J8 k9 _1 h7 s6 o8 g" E
case 1:
+ O+ q1 o. ~1 P case 2:
' j* U' M# N& j' ]7 ?$ g Formula[len] = cSym[Sym[j]];2 g" y% G! J5 S% _9 l, {
strcat(Formula,temp);
# K/ q w0 [* I, D, P- q break;
: T& b! {9 v5 i1 g8 V& w7 S case 3:
9 a# a9 g; d. A* q8 H case 4:
* u$ V% i. r8 l0 ~% N1 a# o7 D; [ + J2 Y; t4 j) ]' B- a/ X2 d
// 如果上一个操作符号优先级低于当前的,应加上括号
' T6 l# ]: X3 O& I4 _5 E0 r: H if(j==0 || Sym[j-1] > 2)* M+ v) i3 _# H0 l
{
- D9 u) |$ C, @6 ]! _: h5 Z Formula[len] = cSym[Sym[j]];
4 p1 r) [) j+ V* c. J# N+ W( M strcat(Formula,temp); C* y/ m& ^6 r
}
+ n& i( E2 C) ?/ x' Q V7 y" K else
# T! M3 s- x2 k8 r9 _8 z+ S {
; ~' I W) v/ {" \ int n;# J; m" |8 J( i" \
char *FormulaTemp = (char*)calloc(len+1,sizeof(char));
; D, F' n) Z8 I' m3 G for(n=0;n, T3 x& a/ l) R- x4 ^
{$ ?! m1 Q+ `1 Q% a) Z" q
FormulaTemp[n] = Formula[n];
3 J! @0 F9 n0 N. h9 j* y5 [- [% @7 y Formula[n] = 0;
4 m* m; m* y9 U5 c5 @0 p }4 o: T' g. z' F- y* x5 {
Formula[0] = '(';2 G3 L q. {! j# ]4 U9 a
strcat(Formula,FormulaTemp);
8 P3 g) p" S1 f$ k; Q free(FormulaTemp);. @9 I; E! f1 \( u
Formula[len+1] =')'; w; p! o3 Q, K1 Z' k7 p) u& _
Formula[len+2] = cSym[Sym[j]];$ j8 V: c4 h2 k2 _& M
strcat(Formula,temp);; I Z0 U2 \4 y ?- K! ^' [
}8 p$ s; i. s8 o, {
break;
. n% m4 _/ H: F2 C( s. Y }
( H# p8 ]) K& d: ?' Z i++;j++;, W V- d) t3 \4 j3 B# Y
}
' z. J9 B1 {( N( J$ j printf("%s",Formula);3 i* e% L. P" v" q5 a
printf("=%d\n",sum);
2 }' V: ?& G; R' p free(Formula);
1 r! r: P( P9 `- n" m }' {# o' H6 B# o, l5 y e
5 E: @; [" h8 }8 G- S
// 以当前数组为基础得到一个从小到大排列的数组1 {) W. a) o) t
// 返回非0表示穷举结束$ d X [1 Q- _2 g
int EnumArray(int *Num,int min,int max,int count)% G, ]4 h9 I. L4 K5 P/ o
{
4 t, V4 T* a1 |. d' S E9 c# | int i,top;
, C, t7 b" W( i3 r top = count-1;( q& l/ R+ F* `% F8 F
Num[top]++;& m5 x% e# U9 j1 J( I
while(Num[top]>max-count+top+1 && top>=0)* E: ?+ ~+ @/ z) c1 @/ [2 K
{4 F% |2 V3 k3 k
top--;4 \2 R2 Q# V2 k) u# l9 R
Num[top]++;
8 q9 n4 G5 H' [- o }# H9 i6 x5 u3 n+ T: u- @$ E
for(i=top+1;i' Z" O: t' v! v6 Z( e
{' k* L& ]# M7 r1 S1 E# B4 W: F
Num = Num[i-1]+1;6 b0 x+ D Y" h- B' Y+ m: A3 Y
}8 ^/ s. v$ Q+ m7 ?
if(Num[count-1] > max) return 1;" q7 X% [$ h9 V/ A2 e% d( w
else return 0;+ O! R( H* W. n
}+ d- Y' T4 r* G7 D1 _
" C8 R. F! v. y* j // 不允许重复的初始化数组; x l/ j9 O/ Z, ~8 i" k
void InitArray(int *Num,int min,int max,int count)
* k: q& D) Y2 c: a6 ]8 L8 y E& u0 \ {4 K% Q5 m1 ~ _# c( h/ a
int i;: b/ j* b$ ^" F" H2 F% a/ s
for(i=0;i=min+i;% p# Y! n: d- b- Y! R) B# C
Num[count-1]--;
- A$ C2 z$ C' b6 f }
( j. K) S9 n* l+ n9 D! M- j. [! h
7 ]/ d- c7 K0 P! `5 A4 H4 {! P% k5 N# A
1 E. H9 }5 \: ?' t" r [此贴子已经被作者于2004-5-2 14:50:47编辑过] 8 ~$ S8 K% G" r' A* b: R+ |
% F) r! i9 p& z8 jprintf("总计%d个式子\n",EnumFormula(1,10,4,24)); 的运行结果是:
' E, k% D/ S6 R. r1+4+9+10=24, P$ ^0 p+ G9 W
1+5+8+10=24
% c; q; O y9 k/ W, V- _. b+ y1 h1+6+7+10=24
' R. L6 s) P' {3 M1+6+8+9=24
# j! w) Y& o6 m- W8 u2+3+9+10=24
: h7 _# h! F$ y. g6 W2 |+ p2+4+8+10=24
( T- `0 a. W6 F2 ~4 C% ^2+5+7+10=24- g) s" w$ U. h& r5 x) V
2+5+8+9=24; o" j8 f0 d; z7 u$ t
2+6+7+9=246 |3 t% I' j, K( R" f
3+4+7+10=24
2 P* N+ E" z& _6 b3+4+8+9=24' `9 o4 Y7 ?* X, e5 I/ f
3+5+6+10=24
3 B9 t; m1 M6 R) Q; E0 F7 l) H3+5+7+9=24
3 W" N9 b& B2 T! \% s$ p3+6+7+8=24
$ E& F9 v/ H# T; E4+5+6+9=24
' y* y% G; z& {- W% l4+5+7+8=24
( r0 X* Q) y( p这是什么意思?似乎是找出了 1 至 10 之间的和是24 的数据,这和完成计算24点,差很多吧?
- H7 T) }4 V& Y0 w比如用户输入 2 ,5,7,8 程序应该能得到计算这四个数据得到24的表达式才行啊,这样就可以写一个游戏了。
: R6 e `) }8 d( [& u& M0 n. @! S如: 1,5,7,8 有如下方法可以算出 24
! a, ]! \) }; }2 o& v((1+7)-5)*8 = 24) i8 ]! l! F4 Z& c* s0 ?
((7+1)-5)*8 = 24
- A+ {& z9 T, O4 ?(1+7)*(8-5) = 24( ^- u" j% j; |
(7+1)*(8-5) = 24
9 ]1 u% V% _: E7 n$ T((1-5)+7)*8 = 248 F) Q+ j4 O" F) y4 T4 f9 J& h
((7-5)+1)*8 = 244 P- i& f) i7 }' Y% v: K3 F
(8-5)*(1+7) = 244 z- f3 w3 d$ p/ w
(8-5)*(7+1) = 24- Q v% p* \1 r' b- A/ B" S
8*(1+7-5) = 24
/ ^6 V" e% q! D& C3 o# s8*((1+7)-5) = 24
' z7 ^/ D3 E6 P# f" z& G& Q( b+ q. p8*(1+(7-5)) = 24
5 u1 s/ v+ D( L B0 l8*(7+1-5) = 24
) P+ L( |/ q2 U- l" e8*((7+1)-5) = 24
% H& Q6 r+ c! J8 |3 k8*(7+(1-5)) = 242 @( t5 @1 s$ Y( f5 `4 M
8*(1-5+7) = 24
, U% }7 @# `1 L% K, s8*((1-5)+7) = 24 y% j- N. y7 J& E& v0 y7 M2 R: J
8*(7-5+1) = 24
. l# @* r9 @2 v+ |; s8*((7-5)+1) = 24
9 X8 x8 W8 x j& L) n8 y# w |
|