TA的每日心情 | 奋斗
2015-9-17 00:58 |
|---|
签到天数: 1 天 [LV.1]初来乍到
|
以下是引用游侠无极限在2004-5-2 14:41:26的发言：
3 N; }! z* r' R. k, K4 I6 _. o#include
3 z3 U8 Q0 ^9 O7 K9 B #include
( i' \7 z/ m( y# G: `/ [ N' c. M% b/ X6 ^6 m! S
int EnumFormula(int min,int max,int num,int sum);
/ _7 v# @3 G, ? void ShowFormula(int *Num,int *Sym,int count,int sum);
# i' S4 v; ^8 c- |0 J2 k1 @ double GetFormulaVal(int *Num,int *Sym,int count);+ K8 r- o' J! l# |- [: C$ T
int EnumArray(int *Num,int min,int max,int count);) \6 D8 d, x7 \
void InitArray(int *Num,int min,int max,int count);
3 {2 i) I# {! @, P! Q! X0 |' T const char cSym[5] = {0,'+','-','*','/'};
& J3 t C& @, v' l( O6 Y& S
6 X" k4 P) m) ~: a int main(int argc, char *argv[])
% c. B0 K' h9 h1 k0 | {
7 O& K9 b% {) S) C' u printf("总计%d个式子\n",EnumFormula(1,10,4,24));: k' `9 [, ?/ \
system(" AUSE");
/ `' B' N, S) F2 d# ^' d return 0;2 m/ M( p0 m/ W
}0 P( G) ?2 J0 |# P% J2 m& V! Y5 N% M0 n
: O1 e) Y( e5 q- z+ z" U4 m' Q int EnumFormula(int min,int max,int num,int sum)+ D9 q$ L R$ g: k/ r2 d. h) h }; l
{
' X3 j% C! Y }$ ?+ c int *FormulaNum = (int*)calloc(num,sizeof(int)); //储存操作数- I+ y* e' @; @: ^ i. N# k+ {
//储存操作符号
5 b4 R K3 t8 q; w //最后一位用于穷举结束标记
5 l) O3 m5 ~9 C6 ]4 U // 1 - 4 代表 '+' '-' '*' '/'* L6 |! w3 |$ K0 U+ Q
int *FormulaSym = (int*)calloc(num,sizeof(int));
9 z+ |: @8 B5 r" J. j% j. q
* F2 |& V! V9 ]3 Y Z: ? int result = 0;
' h( D/ u. [2 J w) d // 初始化操作数和操作符号数组6 M. j0 {& m, O O
/ |! Z) d5 p9 K6 H8 N
int i;+ N: W0 j6 Y8 P1 P n" A' U
- B1 F+ h. W5 T2 ]! h% Z for(i=0;i = min;
8 b. v( r M1 j& r& a3 @ for(i=0;i = 1;7 d& L5 x8 _9 l1 i- p" d
FormulaNum[0]--;
- o9 S8 X& |$ |! T @2 M+ t6 x# F/ D4 D E- c$ M# b
InitArray(FormulaNum,min,max,num);
6 A, H& N3 O6 I3 [0 v, g$ g FormulaNum[num-1]++;) M; y0 ?& s9 ?# N% L0 y
// 穷举操作数和操作符号组合5 c# @$ u H9 g( X
while(FormulaSym[num-1] == 1)- y9 |" S0 W# I3 \; P8 S0 \
{
1 x0 f" G7 P ?8 ^ double t = GetFormulaVal(FormulaNum,FormulaSym,num) - sum;
# l K9 t4 L& z- c6 \$ b, X+ q if(t>-0.01 && t<0.01)
4 P7 ^; d3 ^+ t8 U' r {. ~, @( m% `1 G$ M- c, u; P! e
//printf("%d %d %d %d | %d %d %d ",FormulaNum[0],FormulaNum[1],7 c3 ~; A: Z0 R9 l+ r9 M% n
//FormulaNum[2],FormulaNum[3],
! C0 @% {5 B5 a2 e5 W* f) P // FormulaSym[0],FormulaSym[1],+ |4 g4 c$ h- y& d* f2 l
// FormulaSym[2],FormulaSym[3]);; X- L: T% @0 ]/ t5 Z
ShowFormula(FormulaNum,FormulaSym,num,sum);
; v- r1 w+ t2 E2 d' L result++;' l7 ~8 [* r3 |* V' r. p3 a8 o
}! W6 Z/ t) I% y! C x( L5 z
7 w% p& q. @# Q# @: V
// 依次穷举操作数5 _7 g. V5 m% {# x, l1 I h- w
" B: S% \" I3 k5 c9 o* ^
//允许数字重复的穷举; `& Y, i( K' k1 s, X1 q
//FormulaNum[0]++;7 z" G* |) ~: P" S; r% ], C% {
//for(i=0;FormulaNum > max && i) z( z; K" }5 W9 m
//{
% t; L# {+ k' p7 g) c // FormulaNum = min;
* Y \( M. O# y: G8 k // FormulaNum[i+1]++;
$ @- a) i+ I! ]# L f //}
6 u" z5 ], m6 v6 N7 p // 操作数穷举与操作符号穷举联接- ^6 C2 L( P8 w D% h8 g$ p- `
//if(FormulaNum[num-1] > max)
' R/ Q7 A I% c) L" U- k //{/ q; K! D8 _; s: v# o% O- M0 b; `
// FormulaNum[num-1] = min;8 ~" r# O% C( |* j
// FormulaSym[0]++;% g( Y3 s; g6 G1 |$ q7 R+ j) m
//}
" c0 i. O! _* T6 B% n( R/ b+ e
8 g i1 j7 n" s A2 y' R // 不允许数字重复的穷举
8 [1 i3 I7 W! b/ I1 l // 数字必须从小到大的排列，防止重复
: E& H' R/ k7 i2 i# s! x7 m2 H" p if((max - min)< num) exit(0); // 出错
% y8 \% }8 f5 s$ e
9 ?- g! y& w4 g$ I" a if(EnumArray(FormulaNum,min,max,num))
: x4 m- R4 D! D5 j {* G! s1 [* g2 n2 J e8 t# \
FormulaSym[0]++; {- B6 W3 j0 @# ~0 A4 q9 S( N. l. S3 C
InitArray(FormulaNum,min,max,num);! y9 p$ S& H }6 ?% {3 q; X9 m( W: ~
FormulaNum[num-1]++;. n0 B9 w5 I) S' \) A' _6 A, m& T$ I1 Q
}; }4 M& s7 _6 m0 n: l* o8 [1 h1 X
, ], ^" J( d# n$ H
// 操作符号穷举
$ ^- v. w$ V, K4 k7 b2 g( b7 j for(i=0;FormulaSym > 4 && i0 b$ e! p5 j k. i+ | {( @& d7 s) K# g" ~/ t
FormulaSym = 1;
9 A: F' |6 b& t! _: c$ _! O FormulaSym[i+1]++;
) C( t- m+ `6 r$ ] }
: v' X* m- K1 s1 I. G ] Z }* v' y6 T, h& c- Y
}8 q/ G) R) J9 h1 X
//释放空间
' g1 ]& O' y! B7 R- O free(FormulaNum);4 h _: |6 ^& S7 i" u" z
free(FormulaSym);; \1 o: h3 I# g
return result;8 M) k0 N) e) k7 O W; b
}6 N5 |6 u- c7 p6 U8 k0 Q( w
// 计算算式结果
+ k, s% C1 Z5 |: V8 D7 Z double GetFormulaVal(int *Num,int *Sym,int count)
) x( ^/ D0 l/ ~4 }6 g! Z+ }+ o {; T8 k3 j7 Q. G% S1 q
int i,j;' V1 D2 [+ t. d# o6 c0 }
double preresult;7 G, u& T! p$ M- j! d
preresult = Num[0];
0 O5 _8 k' _7 }: d9 @" a; r i=1;j=0;9 b6 k& d1 ]" P8 O; x
while(i6 k+ E: ]9 I: }5 U( t; W* N {) b4 i3 l7 W, n# w* ?5 b
switch(Sym[j])
, p% B6 s+ g: _4 L9 W {/ a0 E' d. _$ l/ K* H4 Y
case 1:
& U4 g( ]& n0 q% ]5 Y9 \ preresult += Num;
# k0 g! D# N; r8 L break;: s$ J# J1 G* i8 k
case 2:
& O2 I$ j, ~4 A5 f" U7 _+ l, D7 j preresult -= Num;
) p! I/ R$ i& \9 F' b T4 ? break;" }. h, }1 l( Y( p6 ]
case 3:
: J( F9 K; a X preresult *= Num;: w; n- D( g5 a) k/ [" y
break;
j5 l& h7 V4 s: q" l1 \ case 4:
- i+ _" ` M. T if(Num == 0) return -1000;
2 T- h4 S( B, `: ?1 o preresult /= Num;6 j! W. j6 H; h3 K# I8 `2 e( f
break;6 w6 Q3 D( S/ j4 ~9 \* t6 x
}
/ ~+ P. d. u) `* D. S i++;j++;
" i" R* Z1 A7 |) m I }
; |8 z# U; t- c! s6 \) ` return preresult; //进行修正
3 W! F0 H3 p7 z) N* X }7 h# @5 q/ _" L$ ?! D: f+ v
// 打印算式) x' n# q9 U- ~, T' F4 A
void ShowFormula(int *Num,int *Sym,int count,int sum)' A2 Z" s) S: r# I( o
{3 q, i1 Q- ]7 Y r# f% i
2 Y0 l* ]3 R7 M7 [2 w1 R( F int i,j,len;
6 f6 C- C, R* V/ K- Q) i6 `& o& C: u char *Formula = (char*)calloc(count*4,sizeof(char));' F1 g: D5 X7 m. D! t
char temp[10];/ l4 c: g+ y, Z+ R
itoa(Num[0],Formula,10);
7 T, y% C' e+ |" i, I0 ^: V i=1;j=0;9 ]' m9 t( O% D+ Q* [
while(i* R8 D- u- {8 n# O {% u4 {4 v5 C" Z2 s* ~* ?3 } f
itoa(Num,temp,10);1 d, }4 f7 _% J% W1 y
len = strlen(Formula);
; G; e3 T5 T) d switch(Sym[j])
0 q+ N6 \ a# e# r- Z% h3 q6 L- Z {1 I. r, m" }. k8 G+ w3 M E. S0 c" e5 U
case 1:4 z4 Q K/ U3 S4 u. `) W
case 2:
! A* {7 F6 U3 f Formula[len] = cSym[Sym[j]];: h: d. l" Y4 R: x& Z% u
strcat(Formula,temp);
% W+ l% a7 K" H/ D; I7 B6 a4 c break;5 G& D# p9 W, l# c6 T* ~- S7 {# o* C/ q
case 3:
0 u' O4 a" w% i% T4 c7 s1 p case 4:
1 F4 b' E. z6 f % {+ N8 g/ H0 h7 g2 w
// 如果上一个操作符号优先级低于当前的，应加上括号
: u5 r9 H2 T7 O K if(j==0 || Sym[j-1] > 2)
5 N: N! X. r/ H ^- P/ }" [ {: |( N9 r# {6 `9 A$ s0 k% W5 S9 u
Formula[len] = cSym[Sym[j]];
9 ]4 v C) v$ s- Q, O strcat(Formula,temp);
+ |% E$ [: E: P" P c }
& k1 L" F- C& K5 s. N- k# r else) t3 x, y# B1 G" A3 ~; C9 u
{
1 m; `% r8 Y% ^% }2 {# u4 | int n;" e9 z6 P0 \9 Y7 R6 Q
char *FormulaTemp = (char*)calloc(len+1,sizeof(char));
% l7 v9 ~- W! G5 D! I2 u for(n=0;n4 s4 u, a/ O7 z0 B- G4 M {6 v2 X' u j: R5 \% u7 o
FormulaTemp[n] = Formula[n];
8 Q* W- }- M# l Formula[n] = 0;
! t. } `+ ?7 t }
' R/ T8 [% S+ k Formula[0] = '(';8 t1 R) e; D2 @) g1 c* b
strcat(Formula,FormulaTemp);
$ _7 z5 c; V: ~+ R5 b free(FormulaTemp);
' X- y4 ?6 u: ]4 X Formula[len+1] =')';( ~- M$ q9 o: q8 `, h
Formula[len+2] = cSym[Sym[j]];2 b+ U. b8 G3 l4 `; Y b4 z
strcat(Formula,temp);
/ S( [% W! x- ~% {. J' ~ }
; r6 l: f$ ]5 X Q5 z break;
* ~; c2 a+ O1 P2 q( C }, Q9 N3 ?. `' J/ x0 ?/ {
i++;j++;& v6 O) W# c' q: J' m
}
; _/ d" c" Z" V" ] printf("%s",Formula);
4 W7 W5 p* X4 w) ]" p printf("=%d\n",sum);1 R( N8 L; y7 \% {
free(Formula);1 n' [2 y' w4 i; N5 U3 A1 T
}
# E' U5 b' E* o& r7 W( Q: q2 [! n# I3 V5 ?" i$ b( ]; ~4 t
// 以当前数组为基础得到一个从小到大排列的数组
/ d( I, q; k8 [1 D, Q# j // 返回非0表示穷举结束/ d; J7 p$ r: _ M0 {
int EnumArray(int *Num,int min,int max,int count)! h7 c$ }) [" P
{
8 Z) h4 C( Q! P3 Z int i,top;6 p @ K* `6 h
top = count-1;4 `8 }% }- A3 d9 V
Num[top]++;
0 Q" R; t; x( r while(Num[top]>max-count+top+1 && top>=0)
& T" _' R3 w$ U& `; b) E: V {
% h0 L9 Y# R) J9 T1 f4 a9 D top--;1 }3 `: |, L( M4 E% `
Num[top]++;
) L, C. n1 ]0 I" r5 O3 v) p }- ^& ?! B8 R% \% O0 g3 r: |
for(i=top+1;i/ s5 c" x9 f1 B0 }4 M1 U( n+ [+ c6 | {3 B+ i) {5 Z) ~! z
Num = Num[i-1]+1;, m5 `# h1 i) C1 ^
}
( k+ {4 ] A* {. Y$ r7 D& ] if(Num[count-1] > max) return 1;0 u/ D4 n) y$ p6 \+ s" X+ y2 T
else return 0;- h; D5 m0 X9 Q, ?; f
}
& w4 w7 ?) A+ b0 a9 P( l# e/ _8 y+ O# R1 V. M4 n' b" n* E# n) J- ^
// 不允许重复的初始化数组
+ ] h! y# e; { `5 } void InitArray(int *Num,int min,int max,int count)2 s# m( ~8 ?5 S& K( f" ?
{
' {' z6 s2 f: c) x" J8 s4 V% { int i;
2 F7 J; ~: X2 r( ]2 Z for(i=0;i=min+i;! N7 f0 `, Y2 w% t$ I5 t4 H' L1 X3 \
Num[count-1]--;
: E- W- v6 q+ m" ]: Z" @0 J/ Q }/ u3 w- y) `) S. w: {' w. Z
* f. v9 C1 @! p7 e
# f% P+ H/ V8 J* F. w
& I, n9 v. b! h$ F8 P2 G' k- z
+ [- I4 W) I( z/ H1 h
[此贴子已经被作者于2004-5-2 14:50:47编辑过] |
|
IP卡
狗仔卡
发表于 2004-4-27 17:53:00
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
分享
顶
踩
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
千斤顶
显身卡
发表于 2004-5-1 09:53:00
楼主
/1 
