|
|
|
#include
) Y, T1 g$ X% ~0 d' H2 E9 X#include 7 w9 U0 ~" }$ [9 n1 G+ B5 P
3 ?8 M: U, d4 ]; ?8 A, ~+ H+ X; W hint EnumFormula(int min,int max,int num,int sum);2 q' w3 p% q. n8 _% Q
void ShowFormula(int *Num,int *Sym,int count,int sum);, J* l. J) N; ?
double GetFormulaVal(int *Num,int *Sym,int count);
# q6 w0 D, ~' F; G3 Jint EnumArray(int *Num,int min,int max,int count);
, b- r+ e/ F f. |/ ovoid InitArray(int *Num,int min,int max,int count);. Q5 s7 j3 v$ c/ {4 x9 N7 ^9 b1 V
const char cSym[5] = {0,'+','-','*','/'};- A* h" w. ?" d; I
; d, ~- w8 n/ f4 h$ B2 C# E
int main(int argc, char *argv[])! Z' r q/ V/ G
{$ U. K4 z/ J: E, Q9 \: T& z% ~& A
printf("总计%d个式子\n",EnumFormula(1,10,4,24)); q- |5 H' l* Z: z/ T# p- U
system("PAUSE");
1 U, d. ]8 N' L( ^% C return 0;
* n* h' D" L3 S% v7 g}2 v T2 o O+ C" g9 ]
- k9 k7 X; Z2 @5 X
int EnumFormula(int min,int max,int num,int sum)
, j4 H( y* G+ k8 S$ T* R) h{' M& p5 l y" z
int *FormulaNum = (int*)calloc(num,sizeof(int)); //储存操作数$ b4 m8 ?# D, W' ?- R# _( v" T3 k
//储存操作符号$ S$ E/ O7 Y9 @& X& p$ Z
//最后一位用于穷举结束标记' G& \9 c, Z* ?5 F; {' [
// 1 - 4 代表 '+' '-' '*' '/'
, H) \ d9 V" K8 L& [2 B int *FormulaSym = (int*)calloc(num,sizeof(int));0 Q9 p/ d @, B8 Z: L8 u8 z
) V4 i: j2 i$ g) f int result = 0;6 G# o2 S% F' Z! l
// 初始化操作数和操作符号数组2 K' `) _( ]( i: o* v
$ [0 T- ^- V1 m* V# M% @- x
int i;
2 h0 A( ~/ s" |/ p3 A& A( k& c, b
0 ~% `: [3 M0 O( C, F! k _ for(i=0;i = min;
* i, d/ w7 Z' [/ t1 l for(i=0;i = 1;; S; p# |! D) k8 P' p) s
FormulaNum[0]--;
|" Y% \% y5 q' \# [5 X- j0 J$ U5 H
InitArray(FormulaNum,min,max,num);
% Q; T' \# ]$ j FormulaNum[num-1]++;7 [- |. i2 F' @, `6 I: ]
// 穷举操作数和操作符号组合
7 T' D. c1 b) T$ W8 O. F8 j while(FormulaSym[num-1] == 1)% U$ X) r, n# l4 Q3 F
{
, p8 ?$ z8 Y8 I: G1 e: h double t = GetFormulaVal(FormulaNum,FormulaSym,num) - sum;
9 ?. N+ g' `& v! r- e$ A if(t>-0.01 && t<0.01)
b, i9 l* _! o4 |: R( Q {
4 R5 O) I4 O2 g9 I4 ] //printf("%d %d %d %d | %d %d %d ",FormulaNum[0],FormulaNum[1],6 Q8 E; O- L ?' J' W
//FormulaNum[2],FormulaNum[3],
8 p# S: q9 d) T+ S+ l. U; l // FormulaSym[0],FormulaSym[1],
! O6 s# X- F1 G) U/ {# G d // FormulaSym[2],FormulaSym[3]);
# ^. `3 s' A j ShowFormula(FormulaNum,FormulaSym,num,sum);
) R5 `7 D @0 a result++;
1 n) u6 }6 Y3 j% c& ~6 |7 C } q7 Y Y0 Y& L/ f
- P \/ g; ~: P. m* g, u4 |
// 依次穷举操作数+ _+ L9 x+ ^2 X! f; s. }* y
7 B' z$ a9 b" h0 _: b% x, A //允许数字重复的穷举
1 I5 J/ k" X0 {. G* ~) q& [ //FormulaNum[0]++;2 m' X+ N+ j i
//for(i=0;FormulaNum > max && i
0 l4 o/ {, F. R, s //{
, i+ x+ O5 y* w1 l: X) ^ // FormulaNum = min;
9 o& W; \* s5 o. f# T* v. D // FormulaNum[i+1]++;3 K U2 S& \# C
//}1 t: a7 {4 L: G6 B4 s( S% B0 Z) A. [: M
// 操作数穷举与操作符号穷举联接$ {2 d0 o* s' r# m8 u
//if(FormulaNum[num-1] > max)/ a; X. o. h" |$ Z
//{( i& c2 x! Q# F, w+ m1 H0 G9 H
// FormulaNum[num-1] = min;
8 t+ W. r+ b2 m4 o+ J- ~% W: W // FormulaSym[0]++;
4 v" S+ H3 w: M9 A* }& Y: W0 [ //}
! h2 y' _3 s% E
8 Q" {5 u& R7 c# t; i4 j- n // 不允许数字重复的穷举
9 r s9 M" Z+ I& s2 H // 数字必须从小到大的排列，防止重复4 l+ E- g9 D' r2 s$ b- c
if((max - min)< num) exit(0); // 出错: k4 ^ }* r* U% Z
% S2 m$ G0 q( \( v( L if(EnumArray(FormulaNum,min,max,num))
+ H, S, f% u3 n! V {* {4 c$ L$ i; f5 F
FormulaSym[0]++;+ v- c8 x' |& m+ Y
InitArray(FormulaNum,min,max,num);
) @) [7 c6 x1 i( G3 r0 \ FormulaNum[num-1]++;& C$ x8 ^) d. N5 h
}8 p3 G, f. Y/ z9 c* X" p. Z/ N* Y
6 T/ d7 c% i- v; b3 `% z& Q
// 操作符号穷举
: s& Z/ y. e2 ^ for(i=0;FormulaSym > 4 && i( _7 e& Z7 U' q; A! \* r" w
{
* Y- o, n6 Z9 c; ? FormulaSym = 1;
# k, x0 l. s7 |/ ]% H) @ FormulaSym[i+1]++;$ T, C- l! L- x
}
! u, q7 V( e1 {8 ` ~. W5 b
r& X e( T$ {) d }- a9 R' }( O% y, b$ D
//释放空间( R& n; \! j f9 y" c9 s( H
free(FormulaNum);
/ J: O/ C3 h5 q# p% B; b- E free(FormulaSym);8 f- X$ V. q6 \+ X& Z8 s2 ~
return result;
' k# d7 z- i8 d; |4 w* ~0 g}9 f9 G; \' ?" P
// 计算算式结果! r6 E3 y9 p) f, v- _9 W
double GetFormulaVal(int *Num,int *Sym,int count)
% V6 @; F$ V- `: S3 a( `) V{
: r ]$ W6 R5 G' b; y6 Z int i,j;/ u- @) M% R3 n, L
double preresult;. _4 K* C6 E6 F) x( K+ e# {1 l
preresult = Num[0];, z$ b0 s: z' W1 J
i=1;j=0;9 i# ]! i7 A6 ~4 H
while(i, P: T8 D) R5 P9 G$ f$ P1 [' `
{; S* g% f w1 h" f& |' E4 J' c
switch(Sym[j])
2 R5 y2 K: K- [% L {3 M5 \$ q% x! \5 K. b; {5 K
case 1:3 z- l. i( Q4 L. p1 V. l/ O. ~6 v
preresult += Num;0 u C$ r9 ^$ \# i q& K4 a
break;
* K5 k/ s+ }3 {& {( B6 I: b case 2:
: E/ C4 F. ?4 y# l5 |# S, E5 @* k preresult -= Num;% p' U8 Z4 e9 n$ e
break;
# C/ V9 n6 M0 I+ v9 F- d; C1 r case 3:
) D' J7 Z* L/ P preresult *= Num;
. j A. ]" E" Y8 S' B break;
( d$ @5 M2 }1 W/ \. }( y9 a: k6 O case 4:2 e6 ?6 X3 j( U7 |) {
if(Num == 0) return -1000;
" i4 D m- G0 c' R# }9 b3 E preresult /= Num;( B! K/ y7 z7 p: l
break;& S) b- S4 n& f5 z. F9 P( s
}
1 [8 x5 ` F: w0 C( J! R( S i++;j++;
5 ^0 Y. J9 U8 S }
# G! M% A* _6 N. | return preresult; //进行修正
. E$ H! X8 `+ u3 p& {% ?% w}
5 B8 r! f3 W/ G# C// 打印算式4 k8 W3 f7 M) j# ^: L
void ShowFormula(int *Num,int *Sym,int count,int sum), M7 \" @& U Z1 G: X# @# R" S$ O1 Z
{0 b4 @) {( a' V3 u- O8 X* K6 q0 n4 @
+ O+ h1 `4 j! }, T, [
int i,j,len;$ N0 C( [5 Z" `6 P* Z0 w. }1 S z% ?
char *Formula = (char*)calloc(count*4,sizeof(char));9 K0 F7 s8 s. N g: `6 D/ Z$ `3 i
char temp[10];
6 @' V3 C D+ x) u: t itoa(Num[0],Formula,10);. r! ?# @/ f$ U4 r3 I
i=1;j=0;
2 o5 k$ k' _6 K! q D% ` while(i5 p' } J7 a/ I7 L8 ~4 ]' `% S
{
4 x2 ?; H( O9 @, S, i2 {) H& N% Y itoa(Num,temp,10);4 J$ M. Z2 v5 Z, T( _* Z. ?
len = strlen(Formula);
9 F9 R5 X5 L# a switch(Sym[j])6 N+ ~. B. o, `! D
{0 d- M6 d7 e- h% d
case 1:
) |8 Q7 C- ?; I0 s" X case 2:- k: G% w2 X! g# y. |
Formula[len] = cSym[Sym[j]];
' W/ [% ]$ h+ V, y7 `) y" A7 ?' B strcat(Formula,temp);5 U$ {7 V5 i$ ~* F3 y6 @
break;
* E/ l) H; J7 y- p* m8 u- K! z case 3:
% _, U# E3 e, f5 S. T$ \ case 4:/ b& B4 @+ L% l% j
, i7 u: _& a% Z# W; S' ] // 如果上一个操作符号优先级低于当前的，应加上括号
2 z# c( T, C2 P, o if(j==0 || Sym[j-1] > 2)7 k! _- C/ N9 w ]; j b: p
{
( k/ X, t& g# g j Formula[len] = cSym[Sym[j]];- G6 B# ~0 ~8 e% a
strcat(Formula,temp);$ }' l* V) ?) P# z8 v% |
}
$ `% W% Q4 {6 K8 V$ B else
. S$ k8 K# z6 W: r6 v {
3 W! ^ I# C5 q4 z) f int n;4 O3 B- O$ o7 d9 Q ?
char *FormulaTemp = (char*)calloc(len+1,sizeof(char));
& R) I) ?# q% p2 l; ]- K for(n=0;n9 K" ^) ^5 V; t; b9 E {, J8 J6 i4 ]# l5 \3 i+ l
FormulaTemp[n] = Formula[n];
/ {( u4 U4 l" r Formula[n] = 0;( m5 n) \2 |# }0 ^& P4 ]
}* D/ ^' @5 B5 w+ ?7 |2 \
Formula[0] = '(';
9 e% Q) H8 i7 y% E( `7 ^ strcat(Formula,FormulaTemp);
* R) j6 h! S$ e |7 o R free(FormulaTemp);5 h$ L) b9 W# Y: `; o; y( ]( c
Formula[len+1] =')';: Y0 _8 h* m# K: c. J! \% `
Formula[len+2] = cSym[Sym[j]];
. T) C5 a/ S- w7 O2 z strcat(Formula,temp);0 D% ^# p& F9 y& h) N; P
}
" m+ _' T& P0 x break;9 P8 c B! z. F/ ?. n0 n, D, ^+ _
}5 f# r- v0 T) D: x! T; f4 j: i, e
i++;j++;7 R [0 j& U4 d! K
}; ^8 Y2 g' A( o ]% ?% ?
printf("%s",Formula);
# \, W: x4 `' U* v printf("=%d\n",sum);6 Q8 Y' _8 [. l. L8 D
free(Formula);8 c4 w( T( T: Q
}7 d" m3 a) U( s* I+ s: V+ y
# ]: W) j6 `( i" R4 ^9 L
// 以当前数组为基础得到一个从小到大排列的数组
* X& H3 ~4 T8 ^# {4 |// 返回非0表示穷举结束1 B% R' x5 _. ]" t7 Q0 w
int EnumArray(int *Num,int min,int max,int count)
4 Y2 l$ d/ S5 c{
8 O3 X$ a1 B1 q int i,top;
" }# V C: B, y/ q9 V% O& w4 M top = count-1;. J3 I" f% D$ p$ M) f3 R2 r* R
Num[top]++;
3 [3 T0 I5 z# a9 \, p/ K' T while(Num[top]>max-count+top+1 && top>=0)
9 ^+ ~9 O! B( _$ r" B2 ]! | {6 u! a( t$ j7 t& [
top--;* c# k4 v* k, V7 }
Num[top]++;1 ^3 y. a* R8 w
}2 V6 \) o$ |, f0 a
for(i=top+1;i; T! d$ ?! N9 {2 O( g* `! p {
8 L% d" P* Y) y Num = Num[i-1]+1;) R' M- `1 a9 T. c# }& a
}
, R! L2 t5 f2 ^9 v* i7 ]# { if(Num[count-1] > max) return 1;
0 ~ R$ j; c2 n8 Q else return 0;' K1 X6 t3 d" V( O/ X
}0 Y# D7 F# \1 c, ^% G- d
' x1 f$ n: H, x, ~: A" f& k// 不允许重复的初始化数组8 x% B+ ?' U% I# O
void InitArray(int *Num,int min,int max,int count)$ v g# w8 X7 P9 C
{
8 i% ]; K# Y% @3 ?# k1 I int i; ]$ ?. c" a3 G% A9 L9 S+ Y" A5 R2 V
for(i=0;i=min+i;' q2 j( e, U1 \: l# O/ H2 u+ u
Num[count-1]--;
5 {7 j: z; u' {( r& g}
2 T& `) S/ A; l2 r, Q' \! G: D$ R5 d5 Q$ ]4 c9 i ]
" ~; R! e3 C1 ^6 Z: g' V0 Z U
& M1 b: p6 I7 x4 x0 _- ~0 }$ E ~1 b/ \/ e6 B, I. o
[此贴子已经被作者于2004-5-2 14:50:47编辑过]
1 ]+ q! j$ `% C5 T3 K9 d |
|
IP卡
狗仔卡
发表于 2004-4-27 17:53:00
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
分享
顶
踩
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
千斤顶
显身卡
发表于 2004-5-1 09:53:00
楼主
AUSE");
/1 
