 TA的每日心情 | 奋斗
2015-9-17 00:58 |
|---|
签到天数: 1 天 [LV.1]初来乍到
|
以下是引用游侠无极限在2004-5-2 14:41:26的发言：4 i/ M5 z8 O; j; q
#include
' ]0 s1 I. b- l8 C #include - K, G7 G i2 U& D8 A0 w% [
. H0 J k7 E$ Y int EnumFormula(int min,int max,int num,int sum);
[0 k2 Q( E+ d+ J void ShowFormula(int *Num,int *Sym,int count,int sum);* y) w# z4 |+ H3 S! b, D! y
double GetFormulaVal(int *Num,int *Sym,int count);
0 Z+ h8 _" z* Z" I' _2 F" ^$ e7 O int EnumArray(int *Num,int min,int max,int count);$ N5 J( ~/ W/ I0 [" S
void InitArray(int *Num,int min,int max,int count);
3 {6 o" m! ^% u1 a const char cSym[5] = {0,'+','-','*','/'};
! H V, a- G; B4 t- W& ? |* t8 O6 g, |* T
int main(int argc, char *argv[]). j1 H2 I7 ?/ a0 S; ~8 Z! E, _
{+ j/ b+ r1 A; F# ?. x$ d; Z
printf("总计%d个式子\n",EnumFormula(1,10,4,24));
. Y0 ^) D1 Q3 B, N system(" AUSE");
3 [" ]. h4 t+ x. @ return 0;
9 C& D0 x9 X1 Y* C }* r+ [2 ?& X/ c( ~* F
+ H4 g/ ]8 h) j* R5 e int EnumFormula(int min,int max,int num,int sum)
8 G# e/ b2 a P+ a8 I. z {/ R! h5 A! n; ~+ |6 ^ i: e& C0 T
int *FormulaNum = (int*)calloc(num,sizeof(int)); //储存操作数8 O: c3 z( i$ s O9 B& R6 E6 O1 m
//储存操作符号+ ]% h5 o$ m0 C" @1 }) V$ H* A
//最后一位用于穷举结束标记
& r! F& N$ ^$ U# k/ d' Z1 B; h // 1 - 4 代表 '+' '-' '*' '/'1 D! G4 ]) f0 \' c
int *FormulaSym = (int*)calloc(num,sizeof(int));1 b3 @: ]9 B% o$ @$ \ g
" [1 V/ z; y2 w2 L _4 Z- M( L int result = 0;, V" ^0 V3 k* t5 T& _. C j. J
// 初始化操作数和操作符号数组" p# d2 I o* Q2 d, {
; D7 ^; @8 n, Y) o% P2 d
int i;1 k1 \( \2 U$ n3 a2 i8 ?
" b! J; ]# E z; ]0 [ for(i=0;i = min;6 L$ i7 ?' \: H
for(i=0;i = 1;; d; o8 A2 W% V& u: C
FormulaNum[0]--;( c x/ A8 y0 }3 Z; k5 Y0 Q
! ]3 ^* D/ p! d+ y! \, Y- v8 E, ` InitArray(FormulaNum,min,max,num);. d0 n: K& c( v0 b' n% a
FormulaNum[num-1]++;" b2 Z4 O0 P0 z% K$ E
// 穷举操作数和操作符号组合
3 I, I d$ f+ d, X& _ while(FormulaSym[num-1] == 1)
" ^" K: }" j) N- Q6 Q! P% l {
' ]7 J& `8 r: k; K double t = GetFormulaVal(FormulaNum,FormulaSym,num) - sum;8 \; L8 H6 }) X/ i% [
if(t>-0.01 && t<0.01)( A' `2 U5 `( u2 ?3 v+ V* i
{2 c3 ?+ ^( t+ M3 ? I" ]. B
//printf("%d %d %d %d | %d %d %d ",FormulaNum[0],FormulaNum[1],4 l8 i3 i0 |4 N
//FormulaNum[2],FormulaNum[3],
& B4 W7 v1 {/ G9 F // FormulaSym[0],FormulaSym[1],, e8 M5 t& t7 k J8 V7 C
// FormulaSym[2],FormulaSym[3]);; a0 [4 f. a0 M# h- g7 |
ShowFormula(FormulaNum,FormulaSym,num,sum);1 e; ?0 B8 s: i6 W$ L+ |6 | W5 p
result++;
$ k+ Y( z8 z: ?' i$ V9 u& k }4 @; s8 t0 m' R7 A( z
$ L, r! P A) t- x: V6 p
// 依次穷举操作数
" c( m, x; T% h3 r" Y' p& ^# s
/ ^; [+ W9 w _1 h: ~) x //允许数字重复的穷举) J0 ]. n* ^* ~( M# G
//FormulaNum[0]++;. Z. p' ?5 q, P4 d. R
//for(i=0;FormulaNum > max && i
S0 X7 Q0 r+ u# W, s //{5 c& D8 O' _8 D* X. P- K
// FormulaNum = min;
0 L6 ]! M3 u/ O5 L // FormulaNum[i+1]++;0 t0 z: e/ ? y; l+ P
//}& z, V. h0 q, B
// 操作数穷举与操作符号穷举联接
7 J# s# _. r' L/ v% v6 ^ //if(FormulaNum[num-1] > max)! o8 v# U; r5 t/ N) }1 f w/ T
//{
% r5 u. y/ z. h: Z // FormulaNum[num-1] = min; j- A+ q! e1 v) I+ I$ }+ p n; y. \
// FormulaSym[0]++;6 Z% v+ Z$ r, ^2 t0 `/ E
//}4 c1 J* j7 M# \$ m7 D- v
; b; S: F$ ]/ y // 不允许数字重复的穷举+ |$ w8 K9 o) k1 ~
// 数字必须从小到大的排列，防止重复
+ ^8 O/ S' H8 K* x8 i if((max - min)< num) exit(0); // 出错
; X0 K' M, p* q6 A& \% K4 b1 @' M( N: @1 t
if(EnumArray(FormulaNum,min,max,num))
! K# ], V6 X" a3 c% W {
3 t( I9 l4 ?( W7 f FormulaSym[0]++;
) W( M8 F, B, \# o InitArray(FormulaNum,min,max,num);
& D* U1 l7 z! O FormulaNum[num-1]++;+ {3 ~3 V* z5 t/ V$ A
}
3 V! Z/ G% }/ G+ \
8 y/ W+ N% u0 b1 v* C // 操作符号穷举# q9 U( M# q3 S# W2 H* j0 q! O1 X
for(i=0;FormulaSym > 4 && i! A9 Y1 k& o: W
{
& ^ v% x D" b m8 W4 T FormulaSym = 1;. K0 x7 V. f* V1 ]6 U+ P8 E4 [" ]
FormulaSym[i+1]++;( C5 s2 v" m# t: H C0 D! Z
}3 ^; o# s% g- ]) a/ v) \
" G- @* B. B8 Y( ^/ k4 w }# C7 B' Y$ N/ y6 |" m
//释放空间" G7 i: J. C k/ }- {
free(FormulaNum);; S) C: m" ]! Z$ {0 t4 V
free(FormulaSym);
# p5 }( o$ K L+ T6 q6 Q return result;
& A2 G4 ? m; Y! O' d# R }
9 \5 M# Z6 o1 X+ K4 B // 计算算式结果5 E% ?. Y" s% ~. i, P% a9 S
double GetFormulaVal(int *Num,int *Sym,int count)
2 p. O3 P4 l: ~, Z: c7 I4 G {
* W/ t% l5 b* W int i,j;
& Q# D9 i Y/ M: T6 z4 n1 Q+ o double preresult;
/ i1 p# P+ e6 D2 s preresult = Num[0];7 z$ U" k! u- m- f( K9 @1 ~$ V
i=1;j=0;
% N: C3 K% ~3 Q2 u* a while(i9 z/ J7 y1 w4 V, A5 z( t/ Q; T
{& _5 J" E( S" G" V
switch(Sym[j]): d- R ~$ t1 c% X
{
$ U) |# Y% ^0 p8 ?2 Q case 1: R; {3 A" b- o( X4 S; k2 R4 x/ [
preresult += Num;$ i, q7 q8 V# o7 E% t3 r8 p1 a8 h, h
break;0 \5 p$ X' G1 M2 i, u
case 2:
* O4 i }9 T2 O9 Z* J$ y preresult -= Num;
/ z7 H5 X; K; R" y- Z! ? break;% t+ E) B, z; ~8 Z5 W2 A4 Y( M
case 3:/ E2 a/ ^) p- Z) f
preresult *= Num;
8 o, z# C5 Y* G3 ] break;# t, B$ i. M6 W- X
case 4:5 @; L5 g- f1 g' n8 J" G
if(Num == 0) return -1000;
, a2 R; B8 h2 t5 g/ t preresult /= Num;+ m' W h- N# e7 K% \1 |: D0 g( ?
break;% }( o: Y) J( f( G9 _5 Y5 F. _
}/ l5 k' a+ T: y" t6 b( @& _3 p
i++;j++;
) f7 B; i& e" X% q }2 C* s+ v. ?' K! c$ M
return preresult; //进行修正
' {: |" _. s& d5 a3 Y) h( c& L }9 c+ K: P2 `7 A
// 打印算式
3 L* l& ]( \- h) i8 I7 @ void ShowFormula(int *Num,int *Sym,int count,int sum)
3 g. [) B5 b# S, q. o/ G. Y {$ l7 H( H6 L7 Y; J
# c% O3 r! [2 L, }% U, g# G/ J; O int i,j,len;
2 Z3 M5 m% J+ e( w char *Formula = (char*)calloc(count*4,sizeof(char));
$ U5 Q+ W c: @8 }$ d char temp[10];
- N! R- y: U4 ]1 o: U* D& Y& d itoa(Num[0],Formula,10);" f( Z! ]( y$ \7 U9 y% J1 z
i=1;j=0;6 S9 J' R2 z; K3 b: J. @
while(i, k% ]9 E/ k" W: b
{; l' ~8 P+ {3 B) N
itoa(Num,temp,10);
; Q9 T& D* q1 M# b len = strlen(Formula);' D$ M+ A7 [6 n$ R6 i+ f# V
switch(Sym[j])3 ]& M9 _ v0 B5 _. E
{
6 c& v1 }( n% N$ d/ d, z0 A case 1:" ?% k1 [3 ?/ y3 T8 y
case 2:5 u3 Q4 m( ~5 @0 n" ~' v7 i, f
Formula[len] = cSym[Sym[j]];
% k- n" L7 P, C$ P strcat(Formula,temp);
* ]' N; O% y" K break;
( e0 m8 O8 m5 U: q' P case 3:# ~0 A5 W9 \, M/ q) Y Y! l
case 4:
1 P( Y2 X# a7 p" [3 j) L: [
, ~6 {0 U4 ]/ V0 B2 b J // 如果上一个操作符号优先级低于当前的，应加上括号- L* x: Z7 ^: g: d5 A, r
if(j==0 || Sym[j-1] > 2)
" B6 ?( A+ s* d! K& \: N) j y {
" _# O! X* Z, a' p1 q" Z Formula[len] = cSym[Sym[j]];
( U3 O% ~3 e: d. h/ J! a+ g" V( Q strcat(Formula,temp);
: k/ Y1 h2 ?6 ~8 ? }
1 H) q! u* C# { else9 o" x5 v& l+ N, o3 k( H9 {% U% j
{
: {6 V( K- ?3 J1 W1 A7 S5 \ int n;7 j3 w7 n5 z5 k1 k$ ^, W$ [
char *FormulaTemp = (char*)calloc(len+1,sizeof(char));& S& [& p$ z# c+ R2 C) |
for(n=0;n; c. ]7 D6 X% ?9 `8 u
{$ H/ {5 a" K. F3 h$ n% I; L
FormulaTemp[n] = Formula[n];
; M, c+ e- q9 a+ m( h" _ Formula[n] = 0;, _- N' A+ u0 W1 c E
}
$ y1 m! z# h, A! ]# I1 w7 h* i Formula[0] = '(';0 k/ t3 i2 G& g: s: Z
strcat(Formula,FormulaTemp);2 E. u# a' o* o- o4 x* _3 q& h- A
free(FormulaTemp);
$ Y7 V7 r+ c; o# G- e4 j+ {3 I Formula[len+1] =')';
7 l- b, A) b# A( g. p Formula[len+2] = cSym[Sym[j]];
, U8 ]0 R' [9 m, v strcat(Formula,temp);
: X" u) p9 z6 @ }# _7 s O0 x; i# r
break;/ |) R8 `, v% h5 u. O
}
# N& V6 j! ?1 J- y0 u) q5 { i++;j++;
h3 L, O6 R/ M/ s }
8 n5 [" c7 O% |2 l printf("%s",Formula);
7 B' z$ ?( s) d* a" b printf("=%d\n",sum);
3 F: C$ d1 k# H y6 y! ^+ ?1 i free(Formula);
9 }7 _( E; V- }( X1 z1 i6 ^. |- V" _ }
: `# X1 ]; ]' Y
$ [+ b) }' Q/ _; E- T5 k: b // 以当前数组为基础得到一个从小到大排列的数组$ B a3 N8 U7 R6 _- u+ v6 T
// 返回非0表示穷举结束
* J7 t% @) w! a, U- e/ x! e* @! [ int EnumArray(int *Num,int min,int max,int count)
/ N& g6 M7 d: N0 m7 s {: y8 ^3 D& e" L& F) R
int i,top;/ e. B/ m8 x$ s* p8 v
top = count-1;
9 O, F8 q k2 j7 X Num[top]++;
8 g4 ^5 H% z j; a+ ^: ] while(Num[top]>max-count+top+1 && top>=0)% X$ K+ _6 z: ~( h# u& \
{! d4 r$ r+ Y- Q+ r
top--;
7 I( ^9 ~/ @& o0 L$ u Num[top]++;
9 N. g0 K% O/ X" n) k8 N } X$ d/ O C' W* Q- c/ w1 i
for(i=top+1;i f2 H5 ]4 i8 f
{; B; z" E9 B8 S- N
Num = Num[i-1]+1;' E. h- `( J' g4 [% X
}
. x* n7 f- h' i0 ^9 T( E4 H if(Num[count-1] > max) return 1;' p! u7 S# N; o$ p
else return 0;& x" C% I* A3 d/ f; D+ J8 x
}
( u- v1 ^' D5 ^/ _/ z5 j. P1 I7 v' f! [ W: ^+ S# f
// 不允许重复的初始化数组6 f4 J0 K, [% g* C; R7 C
void InitArray(int *Num,int min,int max,int count)+ o/ m6 W+ {+ B; U
{
+ Z9 C8 i3 z3 i3 Q" z: J int i;
! i: Z$ T% z3 ? H for(i=0;i=min+i;
9 c. \' q" K0 d: m$ Y& M0 a Num[count-1]--;
5 K# }! I3 }: T }% i2 ^7 V3 n6 Y
2 X6 G# j$ Y9 ~* ^5 b8 N. ]0 s& { ) ^" Y) D7 f' S2 A2 D( I
4 d6 |( R" S3 y1 \0 k
( i* G5 T8 ~+ r+ H; p- C [此贴子已经被作者于2004-5-2 14:50:47编辑过] |
|
IP卡
狗仔卡
发表于 2004-4-27 17:53:00
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
分享
顶
踩
转发到微博
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
千斤顶
显身卡
发表于 2004-5-1 09:53:00
楼主
/1 
