TA的每日心情 | 奋斗
2015-9-17 00:58 |
|---|
签到天数: 1 天 [LV.1]初来乍到
|
以下是引用游侠无极限在2004-5-2 14:41:26的发言：6 g2 d" w6 t+ T, \
#include " n4 C. m% B& {; c( D. Z
#include
8 {# h0 ` J& V; n1 ], v1 y/ r: T" x8 v, S+ L
int EnumFormula(int min,int max,int num,int sum);" Q9 p$ z: i5 B7 G! s( l& b
void ShowFormula(int *Num,int *Sym,int count,int sum);" J* p! E2 _7 c$ k# y! {& R; o
double GetFormulaVal(int *Num,int *Sym,int count);
' R0 P# _! x1 Q! v& Y. ^* O int EnumArray(int *Num,int min,int max,int count);
j9 ^2 W: Z) T2 W) ]+ p3 P: t; m void InitArray(int *Num,int min,int max,int count);$ j0 N( j+ K$ j% T. A. N C5 C
const char cSym[5] = {0,'+','-','*','/'};
. M( J2 q# `/ |( c( r/ N4 Q: e# n8 i6 B$ @3 b% F
int main(int argc, char *argv[])9 P" U- _. S5 c6 Q1 ? s
{
$ L! S" `0 J+ o0 h7 e" Y2 `1 v, i printf("总计%d个式子\n",EnumFormula(1,10,4,24));/ b k: g/ ~6 \% b. T# ~
system(" AUSE"); ' [) m. V1 w. k/ J0 t% v' _, z
return 0;
0 M- f( R/ r5 ^ }$ E' p( O! D# B) e+ @) J# y
: r1 a2 D* E! `1 f- s int EnumFormula(int min,int max,int num,int sum)# q0 K) T" a2 v" W
{( H& ] a0 |! a+ w
int *FormulaNum = (int*)calloc(num,sizeof(int)); //储存操作数- w# e( h% |9 b* Z; ^0 @
//储存操作符号
+ y! z; ~2 O/ e$ Z% v0 Z //最后一位用于穷举结束标记
0 S( C' m d5 g8 o4 c/ J0 f // 1 - 4 代表 '+' '-' '*' '/' D- P3 y9 v) v8 o4 J( i; B- B
int *FormulaSym = (int*)calloc(num,sizeof(int));
/ w% ~; J2 T! g: z5 A+ B7 s @* d6 z9 p; x W; \9 t
int result = 0;
1 T: `1 @$ t* X; E% s& t // 初始化操作数和操作符号数组
) q C$ X- ^6 k: M
" [ x) ~; E k( e- U! C int i;
* r0 Q. I9 @* S7 y1 f
1 I* q2 z) ?: [ for(i=0;i = min;: Y1 ?3 ~' |3 v* R
for(i=0;i = 1;; f/ E6 \) P% p3 G5 e- Q* v( q
FormulaNum[0]--;
' a$ l" r# Z" B! l& H& O; {+ z- N) Y" d% {& s7 T
InitArray(FormulaNum,min,max,num);; s) \0 H0 v( L7 B! l
FormulaNum[num-1]++;, @. r. m1 Z4 W2 O. Y* c
// 穷举操作数和操作符号组合
6 ? ~! {4 I' M, ~2 k$ x G0 ] while(FormulaSym[num-1] == 1)
/ k: _: w9 h4 | {! e$ |' h+ Z6 j( o" s: w
double t = GetFormulaVal(FormulaNum,FormulaSym,num) - sum;- M B( _9 z; n: G) h
if(t>-0.01 && t<0.01)
/ [& r+ _& F' W+ P8 l- M {2 i$ {2 @( I, k) L
//printf("%d %d %d %d | %d %d %d ",FormulaNum[0],FormulaNum[1],; G4 [* U* x) x/ t" @, K; w' w' K
//FormulaNum[2],FormulaNum[3],4 H- N6 X" Y" n/ B: P! G& c
// FormulaSym[0],FormulaSym[1],
( y4 ?$ K7 ~( j7 {: X4 C // FormulaSym[2],FormulaSym[3]);
" Z4 d# S; G A) O2 h ShowFormula(FormulaNum,FormulaSym,num,sum);& A6 s i. n- H$ b5 B$ [
result++;
! W( i) l! I8 T, a& E8 j5 x6 [ }7 r% W8 [3 y$ K1 t- z5 @
0 q9 n9 T& c" y
// 依次穷举操作数
6 M2 h! m6 i% r( H5 a
/ G8 Z0 f+ f; ?+ ` //允许数字重复的穷举
- x5 G/ P! {* M) W I //FormulaNum[0]++;' @# j/ N0 {( Z0 u
//for(i=0;FormulaNum > max && i" F4 q. }, C4 Z/ V. ]
//{6 X. e9 e$ F5 y, d: q4 i6 ~
// FormulaNum = min;
" F, }3 s4 [9 ? // FormulaNum[i+1]++;
' K* Z5 O! Y- T, x! x* k/ f //}
" O) `. e/ t: x0 N, c& p // 操作数穷举与操作符号穷举联接/ z3 Q) C! [6 M/ @* ]8 q4 Q
//if(FormulaNum[num-1] > max)
/ K6 N/ }3 v2 ?, r2 h- W1 E //{$ j G7 a. P P% C1 E6 T: P7 z6 O9 \
// FormulaNum[num-1] = min;1 B" Y1 L3 S2 G1 T: O/ r! x
// FormulaSym[0]++;
- |& g2 s, F: a- D2 T1 A9 U3 I t! p //}1 Y& I e% r. d
) V' k0 A. c" u! L- ~2 o6 v. ~$ ?
// 不允许数字重复的穷举. c C( f. |( K2 c0 P0 p
// 数字必须从小到大的排列，防止重复
8 w2 `. m% `' Z8 Q& a1 z) i if((max - min)< num) exit(0); // 出错4 e: n* o1 p4 U, a1 @
' j' `. y: v& t if(EnumArray(FormulaNum,min,max,num))+ S5 b% }* p5 N- F+ F
{8 |) L0 x# S3 z6 `( ~
FormulaSym[0]++;# b! `5 _7 L$ P5 Z! f
InitArray(FormulaNum,min,max,num);8 K! P; h3 a1 T: Q0 m
FormulaNum[num-1]++;( e+ O6 y8 M t4 I/ ~
}0 ^. u4 Q) |$ o& w" x/ r. {& v
4 d% ]' J, _; _3 [, v
// 操作符号穷举
7 k" L$ R0 a3 l for(i=0;FormulaSym > 4 && i. Z) V% `8 T$ p+ J {+ g( q1 d; T+ }. M
FormulaSym = 1;
6 I* {* Q! t9 A' { FormulaSym[i+1]++;0 O4 u% p& v, l7 @ s9 T
}2 N: b& R# U# T7 A7 `' n
) ^5 ~; E4 h5 n) B* q3 x
}
/ d/ D$ t' i/ @# {$ } //释放空间4 S- S7 [# y/ P6 D6 \1 Q
free(FormulaNum);
% D7 I# h: x0 n free(FormulaSym); P; a- M( J4 j: u0 R' X+ V# b
return result;
9 s+ ^3 T) P4 \8 `( z+ y }5 w% t3 L' [( Y) L
// 计算算式结果/ q9 s' e$ G; H- Y" I: K
double GetFormulaVal(int *Num,int *Sym,int count)
, g4 y" J* ^- x- }/ I { V6 g3 p$ c/ Z8 }4 O c
int i,j;
+ U5 d9 I+ M* n; O9 A double preresult;
( h0 v% [3 z" ~1 O preresult = Num[0];
* r" y. [0 l5 M1 J2 T4 ~( M i=1;j=0;
* |4 n* `8 A: o+ ~' U4 f while(i$ k! ]; t8 N* i" a3 \! g4 @5 V
{
1 _2 {$ X) I" Z8 X$ i switch(Sym[j])
! I0 j% o7 a0 \ {
1 I) j" T& q( C case 1:- }- M5 G9 P, N
preresult += Num;
& Z7 Z$ Q4 R3 H' m( l3 g8 r1 K+ ] break;
' \! v* m& C2 n& B case 2:9 M8 j# }) Y7 i6 M. X8 M o, w
preresult -= Num;- \$ }3 m$ e2 k& x1 O! c, n8 i
break;$ s2 K' c0 ^7 ?& x7 q% a, K6 o- Q
case 3:% r( ~4 w' c% o; \, i
preresult *= Num;
/ Z0 ~2 G+ _% E/ S2 a, ]" M break;
/ r; x8 M! J3 E case 4:
|6 p8 }# w! _5 F7 z [1 A2 k if(Num == 0) return -1000;
( R& R& t, m% Y; p preresult /= Num;$ c0 R0 v# A6 p+ P0 m) L
break;
" ~. j# {/ \- M3 m }" K% t) \; X2 Q3 U
i++;j++;
& D2 M5 Z) l% P1 p) @ }
8 o0 z2 Y4 o& C. q return preresult; //进行修正8 H4 \4 m7 D9 K/ t
}1 O* G, ~- Q% s0 [8 K+ \
// 打印算式
% A( D( l2 b- s/ @ void ShowFormula(int *Num,int *Sym,int count,int sum)
+ ~: D5 @1 a/ c6 w% d- j8 c {, s* |7 h2 |/ e3 I7 _
' \8 Q! G$ Z; k) z% e int i,j,len;
$ }0 s) I0 u: D9 z char *Formula = (char*)calloc(count*4,sizeof(char));
7 J* Z" l0 w2 F3 \$ Q char temp[10];1 ^" g' C! ]) K* F2 j
itoa(Num[0],Formula,10);4 R4 g+ ]. p* e0 ^
i=1;j=0;! e) y* {" q2 S% [3 w2 Y# ^( v
while(i' W7 E$ W, D7 r7 @, }
{' E2 r/ U: ~$ q. v# |5 z# i
itoa(Num,temp,10);
/ ]$ l1 V7 \6 C, b; t4 } len = strlen(Formula);( J* O3 [1 G' I6 ~; q# `
switch(Sym[j])
- P8 S- O; l: g: F( a9 ^ {' }+ V- ^: {4 j. {8 P0 b
case 1:5 f D$ d, W7 B' h9 ^ d
case 2:6 I$ U7 i7 {8 a' I# d- Y- H
Formula[len] = cSym[Sym[j]];) f, `& x6 f4 X* \; d
strcat(Formula,temp);
7 \+ y1 g0 n( `3 X1 m1 N break;
# K+ Z& f4 V' {; Y% W3 W case 3:0 s# t( y& k% T* w. X
case 4:
0 C0 s( d$ M1 G: | @9 a
a" B3 m2 M* o ~ // 如果上一个操作符号优先级低于当前的，应加上括号
; I m' T3 i' t if(j==0 || Sym[j-1] > 2)2 t% | b8 p9 G. U; l
{ ?2 c2 I' n( B8 S- n
Formula[len] = cSym[Sym[j]];. `# ]: t: p4 Y: e5 O' {
strcat(Formula,temp);
$ D4 `( |" n7 e2 U }
2 {# }! o5 C' \8 T i; o$ Z else
+ F8 y& r8 L7 Q3 n. d {
0 O6 T4 n$ i( V* h( r2 g7 y int n;4 Y) v3 R9 o5 L, O$ r5 U% T
char *FormulaTemp = (char*)calloc(len+1,sizeof(char));- i. _6 q5 O$ R3 _! V& b+ Y
for(n=0;n7 C9 f/ e/ ^: M& [2 o {6 R& N& l- e- V. D4 E
FormulaTemp[n] = Formula[n];
( [; R4 t, }% O4 x! o Formula[n] = 0;! U+ Z0 D& r3 e9 Y6 [3 \* P6 J
}' |" ?$ f) _/ R" t- Z/ z
Formula[0] = '(';
% Y0 @6 o* S t: n* e, o strcat(Formula,FormulaTemp);
9 x& h2 w- j e- u free(FormulaTemp);
% M( p: f. M, D7 H( P. I Formula[len+1] =')';
" P( B. [6 T ?% P Formula[len+2] = cSym[Sym[j]];+ E7 b' \" i2 E" p
strcat(Formula,temp);
* m' u0 R) z; Z& m1 v }" j: W3 N, E c
break;
- T3 G+ _) ?% }9 t7 v4 B# f }
X1 N9 z+ D3 [ B7 } i++;j++;
5 L8 r! A1 w) I+ g }" ^$ y$ ~/ F9 V" i0 q/ j
printf("%s",Formula);' h$ e5 B% Z* ^- `6 i
printf("=%d\n",sum);
& ^( I4 u8 N5 ]2 Q. s* g4 B9 X; n free(Formula);
' m( C9 v7 r* ~; A }) u4 p6 G, S' m- x
) ]2 F7 Q* v2 c( T
// 以当前数组为基础得到一个从小到大排列的数组
! _4 V7 r# B0 P" h3 S& T- q: B // 返回非0表示穷举结束
9 s+ D8 a! R% O int EnumArray(int *Num,int min,int max,int count)9 |$ R3 |* o6 z5 m/ y
{. \% h3 u$ A' E: ~' s5 P# k
int i,top;* i; b5 {. ~2 Y- w" r$ D
top = count-1;/ f6 N y4 Q H+ v7 o
Num[top]++;
& j# F! h0 ?1 A6 w3 M. H- K6 [ while(Num[top]>max-count+top+1 && top>=0)
) Q% L# |6 p/ H- O# b p/ ` {" s m6 }9 o, C9 j' F
top--;) G! D( z6 {4 A# G# a
Num[top]++;1 V$ E& M c3 h
}( X) r$ r; [- e# o0 _
for(i=top+1;i2 @: i/ l* j& r; U) ~) G# ^
{
$ W9 F1 K) j! G Num = Num[i-1]+1;( K( {% E& B) E: _
}
9 Y( c9 ]6 H3 c# r6 o+ ] if(Num[count-1] > max) return 1;
# g0 ^4 X R1 O2 a, o! q% [ else return 0;8 ^/ y- e7 G# ? K9 ?( R( G
}8 ^# u1 z# F1 @2 @! y' W' P
$ L& I, c9 |- a7 i // 不允许重复的初始化数组0 u k% J n" a( u0 [. e
void InitArray(int *Num,int min,int max,int count)+ D" S/ G# R3 u8 W
{) q: f' v; \2 v! [: D
int i;
9 X0 r) N' ]) f {! B2 H* L for(i=0;i=min+i;
+ D6 S$ {% B2 Y8 _9 k2 ] Num[count-1]--;0 e& ]* _& U) _# C
}5 c7 E# S7 i8 _
2 w5 L0 v3 d( X. X( p1 D
4 _" r. o: B) Q- o) ]( l" p( E: {& |# k, i8 _1 S8 n. t' o: {# Q* I
; ?7 ]0 D P0 o4 V: v' c# ~7 Z1 m
[此贴子已经被作者于2004-5-2 14:50:47编辑过] |
|
IP卡
狗仔卡
发表于 2004-4-27 17:53:00
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
分享
顶
踩
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
千斤顶
显身卡
发表于 2004-5-1 09:53:00
楼主
/1 
