TA的每日心情 | 奋斗
2015-9-17 00:58 |
|---|
签到天数: 1 天 [LV.1]初来乍到
|
以下是引用游侠无极限在2004-5-2 14:41:26的发言： n2 Q7 L0 l) @* n" j
#include ; R7 B( }$ s! c9 `$ A' f
#include
) Z% E) J( \: p
/ j6 [ Z7 E: u9 I$ _0 i1 r int EnumFormula(int min,int max,int num,int sum);
: s4 u5 y8 v. g9 _ void ShowFormula(int *Num,int *Sym,int count,int sum);
( M- D9 b6 d5 r* B/ |7 j# d double GetFormulaVal(int *Num,int *Sym,int count);+ [2 H: v9 t) v$ X0 t" T7 P0 [
int EnumArray(int *Num,int min,int max,int count);. F* q2 f n' u
void InitArray(int *Num,int min,int max,int count);. b: E: w% a+ `; ^3 _! e5 M
const char cSym[5] = {0,'+','-','*','/'};# Q6 n8 q9 E& f C3 _
- \9 ]1 T) D9 Z3 i; b7 P
int main(int argc, char *argv[]); j8 s0 T. u' ?. ]1 q5 ?8 z
{
% V) J2 d& `0 C% z printf("总计%d个式子\n",EnumFormula(1,10,4,24));
! ^' V0 z. u& M3 |+ B* G system(" AUSE"); 1 o O9 w( q0 U5 [( _+ |
return 0;
+ G7 g! Z+ S: t- U& n }4 f; y6 K% [- f F z2 Q2 n
$ O0 t: B; ~: u7 y( f
int EnumFormula(int min,int max,int num,int sum)
4 X6 Q' B: K ~9 b: P: _% V& e( R {
" V! [+ w o' T" b int *FormulaNum = (int*)calloc(num,sizeof(int)); //储存操作数
6 S. P# F4 X2 u1 a/ j //储存操作符号
2 W; v$ Y7 B* }( }9 u //最后一位用于穷举结束标记
0 z+ C7 j* ]* _0 {% q7 d+ w C // 1 - 4 代表 '+' '-' '*' '/'
, n R r+ K6 r5 L) T5 e4 \ int *FormulaSym = (int*)calloc(num,sizeof(int));
' \ [7 V# w' h4 g- s
. k0 Z# {5 B* ]5 @' M3 ~7 d, ^ int result = 0;
4 Q" {6 n- W) l5 B# {) u7 ? p // 初始化操作数和操作符号数组
$ v& p( q. M* B* L0 [ 5 g' D: @% J+ F$ N) \4 j
int i;
$ \2 U y+ [* w5 @, h. }2 F4 X1 n2 A
for(i=0;i = min;
# J, n6 i4 [$ J! o for(i=0;i = 1;
& X" p( D7 [9 Z4 C. { FormulaNum[0]--;
/ f$ A1 h0 A# i) U1 g' J+ ?( ~2 f7 ]7 H3 h
InitArray(FormulaNum,min,max,num);
" P, q. C# q0 D* [- K, r' O% @ FormulaNum[num-1]++;
! @3 U, _2 G. k) F/ G* v8 w) d // 穷举操作数和操作符号组合1 u* ^* j* T; P
while(FormulaSym[num-1] == 1)1 O2 M# k$ l. g/ @8 g
{
0 Q/ S5 j0 ~3 ^, o. O% R: E double t = GetFormulaVal(FormulaNum,FormulaSym,num) - sum;
7 ^1 Q2 \% b# k2 m# g3 N4 s if(t>-0.01 && t<0.01)
* M2 \7 k& y- Z! X: h" u' |% E {
* F* Q4 z3 d# I5 ~5 q0 t" k" a( | //printf("%d %d %d %d | %d %d %d ",FormulaNum[0],FormulaNum[1],
. \, j2 L" b( p7 g7 ~& V //FormulaNum[2],FormulaNum[3],
1 r/ o1 |9 P6 j // FormulaSym[0],FormulaSym[1],. j+ z! W8 e9 D
// FormulaSym[2],FormulaSym[3]);4 F6 u: j! r+ S; [% l
ShowFormula(FormulaNum,FormulaSym,num,sum);7 ]0 k v# W) o9 i+ J# y+ t
result++;
; |' ?; X, q3 N9 l$ |2 u- V }- A0 a! D: z5 U7 q. H# B
+ h) R% E" C( O. D3 M
// 依次穷举操作数
. J! T- D7 u9 d4 I- c# i. N
3 v/ H/ o- k) g6 U6 w0 o, @ //允许数字重复的穷举
' {) |1 V7 @7 E+ W //FormulaNum[0]++;
f( c( @! t: b, m; W2 ~. o //for(i=0;FormulaNum > max && i
: p. r& h( M0 U9 ^1 K0 D //{
8 r2 O S4 u$ H1 w' ? // FormulaNum = min;
8 e9 n' ?: ], T; A8 P# ^6 M // FormulaNum[i+1]++;, q+ V+ X9 v) d
//}9 i$ a) ^5 B9 Z4 A5 A
// 操作数穷举与操作符号穷举联接
0 _6 ^4 b" K+ |& g //if(FormulaNum[num-1] > max)
( r/ r# G: l! p( U# t5 Y //{; x) e% [$ m0 {% j
// FormulaNum[num-1] = min;3 z$ s8 ]! B' ^, \
// FormulaSym[0]++;
0 R2 ~3 h! I5 L1 s% B //}7 l0 x. i4 u! G, v8 k
7 H% b( S, ]' _9 R6 s/ I // 不允许数字重复的穷举
# r/ n* T+ Z) s; }( j // 数字必须从小到大的排列，防止重复; ?! ]$ s9 e* I$ R. |
if((max - min)< num) exit(0); // 出错
0 }* q4 Y, P+ B6 D) |/ F |2 {. _6 @) }" g
if(EnumArray(FormulaNum,min,max,num))) z' ~" ?- x2 `: r" {: l
{; a! l& S3 `8 l7 N3 w
FormulaSym[0]++;
9 N2 J! u$ m4 T' ^" o/ B InitArray(FormulaNum,min,max,num);5 F& x: T+ b+ }! w4 b q
FormulaNum[num-1]++;
" U8 t' f7 @& P V/ F) ?. a }
7 s ^0 ?% J- f : H3 N. V; h5 g/ \3 G! C) v/ i
// 操作符号穷举3 q% P: {5 k/ v' f& X, e, X1 B8 r
for(i=0;FormulaSym > 4 && i7 }' R2 u- e9 \ {
8 K4 O) I4 _$ c0 c2 ] FormulaSym = 1;
& A5 n" j9 A) F' k FormulaSym[i+1]++;& Q/ ]0 g& k2 K) m% N: R
}
# W( ^5 \ X3 T+ T. f& U, u; x' J& t/ B+ @
}# ?8 r) p' P* z7 x7 P
//释放空间0 }5 D9 }0 Y( d. `& J; b
free(FormulaNum);
3 d6 T' }# u+ z free(FormulaSym);, R3 ?! B5 F% k0 ]3 o# \2 E
return result;
3 x# U7 O/ K9 ` }1 a" p: J# V* N
// 计算算式结果
; g( B/ l, z% k double GetFormulaVal(int *Num,int *Sym,int count)2 v' B5 p' s2 i5 _
{
. U+ z* y( }4 M7 u. b9 x& e int i,j;4 Y6 e( O8 n5 q2 U2 N( ?
double preresult;; J/ _- }" V L* }0 Z0 W
preresult = Num[0];
/ F4 H5 O" ~& R) W4 k5 y9 G1 W' F i=1;j=0;
$ B, X- R: ]2 G3 q0 s. C2 q R while(i9 l1 r) J: s( Z- Q/ R3 P
{
2 q+ `1 Y& Q& r: N( V5 P2 i4 g5 e+ Y switch(Sym[j]): K! W; r& f8 {9 Y2 M% A% {
{4 T4 s# P. Q3 K' L& F! I
case 1:9 [/ i- z; l+ h b: I+ S6 P5 E7 X4 x
preresult += Num;' y4 m' I5 M& W/ E, n
break;8 ^4 N2 q& f# y7 u" K* ~1 T5 W
case 2:
, r) {7 B. B A: B) X& ]5 i preresult -= Num;+ s! u9 q u# Y) e% ^' r8 w
break;
- C4 A# C# x" l" H" O) {( K case 3:
- y2 J8 X# |5 Z* w: c1 ~ preresult *= Num;
0 m& E! x6 o$ E0 w& f4 ^' b* ^ break;
/ l/ b, Y$ g% o7 g" F% o case 4:
- d+ | ?% F) V) \: R if(Num == 0) return -1000;9 a4 j6 Q: U- d/ b3 o5 W
preresult /= Num;1 a( _" G( u' _. A
break;3 {( G( [2 ?- C2 m
}
# x2 f* l. a% h1 z& \+ c) D i++;j++;
( A1 `( @4 F4 _9 ^+ _; i8 z }
6 J4 e) Y% m4 k4 g; j return preresult; //进行修正
. K: J) j* J4 A" i$ _) @ }
$ d3 X! c0 r' v: q* O: b& A // 打印算式! G; z. i9 f6 O
void ShowFormula(int *Num,int *Sym,int count,int sum)7 s7 |" O: `' `$ |8 c- W
{
0 U M0 I1 h8 O2 O; ~+ U
/ M5 [0 M1 n: ^1 I7 r# m3 L6 C' A2 p int i,j,len; z w6 h- u! Y' f" M
char *Formula = (char*)calloc(count*4,sizeof(char));# ^' ]3 Q! s+ O! V7 j: H
char temp[10];
9 b' [1 z- n+ A* _ itoa(Num[0],Formula,10);; } P! v% T4 g* [
i=1;j=0;
& ?/ w9 E! f$ E- Z1 A0 T2 n8 ~6 M while(i5 d8 k u$ |9 ?; Z {5 B6 p* m$ ]" y0 p/ Z9 r2 L
itoa(Num,temp,10);
) R0 F, p1 R0 |9 d+ {6 U len = strlen(Formula);" K! y* x* p# x+ J9 U5 s
switch(Sym[j]), k8 `. ?! T: J! x9 o, c& A5 w
{' r) u3 d& J' L. ^8 i
case 1:
+ w5 D% M$ Q) E4 ?* w0 r; j case 2:4 o( T, z# U# C+ T, \2 w
Formula[len] = cSym[Sym[j]];9 z' N) J+ M" V4 [1 y4 ]0 K
strcat(Formula,temp);
$ \4 o7 t" I) @) f7 W9 _. | break;2 W0 @- _4 y# t4 N; X6 m
case 3:' F" o' Z) B1 g
case 4:
2 H5 _9 B z" A2 g/ W! w& I 8 p. C8 r5 A- x+ u
// 如果上一个操作符号优先级低于当前的，应加上括号" H3 ~/ R4 a; f# W
if(j==0 || Sym[j-1] > 2)
/ L Y1 s7 G+ Z& x" S: s% l# u* M. f {; `7 d: L Y! \) n
Formula[len] = cSym[Sym[j]];
5 b9 P O& d+ _5 j; ~- x: F strcat(Formula,temp);. T4 s* _% e) w1 K* @
}
# ~6 k8 B2 o0 ~% l else
& C) v' |2 T8 i) u' t6 y+ Q {
/ a' _8 y5 p' t- b6 z* h% [ int n;
; X- f V7 ?9 x" ?; V3 v; j8 E char *FormulaTemp = (char*)calloc(len+1,sizeof(char));/ O Y& j( w- [% l& I' X6 f
for(n=0;n8 v) b3 {/ ?# h {# \) M' P7 f% k; m5 H( b8 \! J
FormulaTemp[n] = Formula[n];
3 b2 C: C# r' Y. g& a4 o Formula[n] = 0;0 m) ~6 C( U* _$ e
}
; A( U1 [: O+ t% w% O* U6 Z Formula[0] = '(';4 @! Z4 e( b* {/ G3 Z2 \
strcat(Formula,FormulaTemp);
' U `6 J: J" ]2 t. v9 ` free(FormulaTemp);
. O6 |9 B7 Z! h- ~/ @$ t# l Formula[len+1] =')';
: |3 y9 a2 V x+ }$ h4 z Formula[len+2] = cSym[Sym[j]];
9 x( G& ^7 r+ w1 E7 g$ F strcat(Formula,temp);
! I% H4 b& G l2 u7 l. ~ }
% h4 D1 h; k& I9 m, N6 l break;6 [+ h# H3 g% N- X$ O; m) ]# y
}8 c* ~* ?! `( S) z4 }
i++;j++;) [: G# S( U) m6 N- a
}
, i$ t. b( @' A. M% O3 f printf("%s",Formula);5 E) F1 `4 D6 m
printf("=%d\n",sum);
4 g- f$ u. M/ n$ m5 P7 w free(Formula);
) S m9 E' _. c! j) [9 a0 h }
, q3 D. C- U) g5 T( m2 t7 x, l" p- D
: \2 ^: e( S& a1 {# s // 以当前数组为基础得到一个从小到大排列的数组: Q- F6 Z1 ^0 `% {9 u6 H
// 返回非0表示穷举结束& V5 S8 L6 G B0 M2 |5 i- f5 v
int EnumArray(int *Num,int min,int max,int count)
+ V% s/ a& R% a {
( h$ F" E/ } h+ G5 F( g- W5 q% X int i,top;' }) a5 Y7 Q$ J1 J; v! P8 q
top = count-1;+ O' x8 Y$ K) X9 G/ D
Num[top]++;
; H- c6 u# B; K: O3 W while(Num[top]>max-count+top+1 && top>=0)
2 l b( L1 n& P5 z {
9 e0 m& M2 i# r& b* e8 Y# H top--;
. b; V6 |7 W. ]) {8 R4 O6 }" o Num[top]++;' Q+ |* |8 h/ ~) R- g# i& L6 g9 X1 q
}0 K, l- O8 d. ?
for(i=top+1;i' V' ~! I" F( ~- s4 j {
6 \' p/ P; u9 D( A4 T& X7 n Num = Num[i-1]+1;9 _( G0 ?) T4 Y. f7 F0 q/ s
}
- n s& U! t2 }( A3 t if(Num[count-1] > max) return 1;# V$ q0 d, } B, ^. L* T; M2 M
else return 0;( J$ ~7 c% L& L: j! W
}' i/ Z$ _# G0 v( ^& c1 }! ~- A
w) P( s( a" X1 `, b" O
// 不允许重复的初始化数组
- }8 C/ {/ |0 {1 u* G5 ~ void InitArray(int *Num,int min,int max,int count)3 N; A D. t; _' q* M
{
0 A$ f- P" h6 g9 u. Q int i;6 Z& p% R9 O! K
for(i=0;i=min+i;
' z7 h# A$ v) F Num[count-1]--;
. y- H8 H. l/ Y& j, H* E- } }
% b: E. D- X0 c! z1 }4 g
8 f+ R- [# q2 e# M , T8 |" L1 B+ |9 r: b
! \3 N4 D1 z& Y) [' N: T! [ 5 x6 _! {& S/ t( R. |
[此贴子已经被作者于2004-5-2 14:50:47编辑过] |
|
IP卡
狗仔卡
发表于 2004-4-27 17:53:00
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
分享
顶
踩
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
千斤顶
显身卡
发表于 2004-5-1 09:53:00
楼主
/1 
