TA的每日心情 | 奋斗
2015-9-17 00:58 |
|---|
签到天数: 1 天 [LV.1]初来乍到
|
以下是引用游侠无极限在2004-5-2 14:41:26的发言：
$ e+ a2 k8 x" j: B/ @$ Q#include ' x! A; h! f) h" {4 M. e
#include
' G( A- P( P6 Y+ E' p8 k' O! a% N
. M( i' S' @3 L: _4 F int EnumFormula(int min,int max,int num,int sum);( f. f1 \2 u& R+ A8 N1 }$ L7 Y
void ShowFormula(int *Num,int *Sym,int count,int sum);
8 ^9 i) [- c" V double GetFormulaVal(int *Num,int *Sym,int count);
* o. {$ Z- w. `) A7 d' U int EnumArray(int *Num,int min,int max,int count);4 J! n2 X' ?6 {7 k
void InitArray(int *Num,int min,int max,int count);4 H+ H5 E- F6 |& B( i" l
const char cSym[5] = {0,'+','-','*','/'};
8 j; @- ^: j+ B$ z0 Q* d# V" Q% q2 b
int main(int argc, char *argv[])
/ F. U% K7 z* q+ U- D& O" ?% M3 x {
* J# l( ^2 j/ l: e! W! _ printf("总计%d个式子\n",EnumFormula(1,10,4,24));5 F" b! X- J% t
system(" AUSE");
7 g6 r: Y: s( V2 N0 a2 c( N7 u return 0;
3 e3 Z5 A% ]% M# v, U) A }1 K+ ]' H0 ^% P u
; ]. B; [' ~$ p# N int EnumFormula(int min,int max,int num,int sum) x/ U' a/ L2 j+ D: o
{4 s& v! \# n: y! l/ A2 T! s' u
int *FormulaNum = (int*)calloc(num,sizeof(int)); //储存操作数# J- J1 C- i1 I; h- l/ H
//储存操作符号1 A+ m5 o; L1 V9 t: z0 `3 r
//最后一位用于穷举结束标记
1 P* b. E& L1 Q1 x3 U' |* D // 1 - 4 代表 '+' '-' '*' '/'
( y& C* \- s. N( P int *FormulaSym = (int*)calloc(num,sizeof(int));3 A! c& h+ c! Z" o* K, i
% i9 e4 v$ F+ m; K1 C" A( Q int result = 0;
2 ?5 K( t- }6 ?: N: f // 初始化操作数和操作符号数组6 Z5 U6 Q2 E* r& Q3 a1 Y
" {! j5 v1 V, o
int i;
" H* T0 F! p( p3 D
& l1 ^0 O) C1 }" f for(i=0;i = min;
& y5 y, j' J( D7 d/ ?& o, [ for(i=0;i = 1;- r' S" J# @0 y. L0 N) V& D
FormulaNum[0]--;( ^" r$ u- v/ G
% E1 @& S. B8 f V; c InitArray(FormulaNum,min,max,num);. A E. o O' z# e" q K/ o) @
FormulaNum[num-1]++;! Y4 r* [/ m5 [
// 穷举操作数和操作符号组合
0 K# c4 A5 P6 [6 t- W5 u while(FormulaSym[num-1] == 1): J& I# p2 y x3 Z: d
{
5 t' E- c5 G/ Q+ ?; s3 p" L: Z double t = GetFormulaVal(FormulaNum,FormulaSym,num) - sum; w7 a, G) a/ S, T
if(t>-0.01 && t<0.01)- S( J! L; g# x
{; K1 M0 n" \4 Q: U/ k
//printf("%d %d %d %d | %d %d %d ",FormulaNum[0],FormulaNum[1],
2 J2 H) j r/ a+ X- \! [2 U3 [2 P- o //FormulaNum[2],FormulaNum[3], G5 Z6 h8 k h- B, x5 u7 B
// FormulaSym[0],FormulaSym[1],
2 l7 T; e; n! J0 K$ }% x$ w // FormulaSym[2],FormulaSym[3]);
; l* |2 J! u! C ShowFormula(FormulaNum,FormulaSym,num,sum);9 J5 ]9 m+ n5 P( }) y( @9 @8 V! w& a
result++;( @, A6 g- h" }- h. c
}, ^% G, f! N* ^ A
3 y8 Q7 d6 k _3 y4 k // 依次穷举操作数
1 s( P8 ^ s) k4 O. G6 W$ b7 b+ I4 p* q 7 { e a% K' ?2 r4 u0 |
//允许数字重复的穷举& `5 E3 r* [4 [
//FormulaNum[0]++; W% P: V% D/ {7 I
//for(i=0;FormulaNum > max && i; e0 J, T+ U: t7 D
//{
- J( Y4 X- q9 R // FormulaNum = min;1 K+ k" Q5 I* C; i3 q
// FormulaNum[i+1]++;
9 ~/ b1 @8 b( z# u. i& T //}
5 F( S9 u' O7 ^* ^# d# o$ ^) W // 操作数穷举与操作符号穷举联接 P* b/ S5 v' x% [. d2 B6 ^
//if(FormulaNum[num-1] > max)
" B! \0 C. z, l' h5 b7 R% }4 `& B //{( N$ C/ F# e* R. p$ o/ D6 N0 \
// FormulaNum[num-1] = min;1 F! u1 u" i: Q5 I' L2 r% y: ?
// FormulaSym[0]++;. V1 W# T2 Q$ o9 \2 T" k& F K
//}
3 z( `* T% m( E+ F5 g( G% W
4 n" A/ W8 m7 X. I4 N% f; Z" K& h // 不允许数字重复的穷举
m- `) y( Z+ w0 P- Q% o5 j: v // 数字必须从小到大的排列，防止重复" s5 G: r* m$ @
if((max - min)< num) exit(0); // 出错+ \3 Q8 u1 d: P; G# v, W
' s& y0 m) Q- C& L, H" \, n* a if(EnumArray(FormulaNum,min,max,num))5 e1 C/ M. @; g. W
{# t8 Y& C! B7 k
FormulaSym[0]++;
8 L. ], {# ]5 j; ~# j7 X; U InitArray(FormulaNum,min,max,num);% g/ M8 _& O7 C# f) W
FormulaNum[num-1]++;1 N% b. J [! @$ R% r7 I
}3 k9 s J, N$ x7 O1 h, O9 G
' s( Y- Z, X( q0 }1 }! |
// 操作符号穷举1 O/ _+ B7 V! G3 r) M
for(i=0;FormulaSym > 4 && i) @4 g9 m4 _, s5 Z {5 ?+ a6 Q' n7 q3 v* e* y# Z/ q
FormulaSym = 1;
2 _7 u3 X/ F7 h1 e FormulaSym[i+1]++;% s2 A& f* X) \* K
} R% d+ |& R! t1 Q; a! Q" x8 _
: ^% s4 n7 I, Q
}2 j" U4 N6 f) J1 g
//释放空间
/ B% k Q$ x1 W1 K9 M4 g free(FormulaNum);
1 }: ~- b' i5 k3 ?8 h! ] free(FormulaSym);' g; f9 m0 x% A8 {. I1 I
return result;
- r' x9 j2 u. I7 M Q! q) q1 k }! m6 T' t' ]& M1 ]
// 计算算式结果
- O2 j0 C% h6 e double GetFormulaVal(int *Num,int *Sym,int count)
1 f% A4 z2 X0 }4 K h {
; G- `+ n, a* u2 S7 }' f; \* n int i,j;
0 H+ D% ?$ T: O8 t3 F" A double preresult;3 ~ U8 X; w" i# d4 Z' r/ w; h/ _) I
preresult = Num[0];* K! G8 e* j8 \
i=1;j=0;
$ x" O+ U: b7 F% @8 R2 W9 u! C2 F while(i% n4 b+ g3 ~, v: J( h0 | {+ S- W) x# D3 ]" @+ O
switch(Sym[j])2 y% h7 P8 a6 `' M# q
{- T* }! |+ ~% Q* M. y
case 1:0 W# c- w P' Y( j( A/ L+ f
preresult += Num;
5 _0 V" t0 h( [8 u: P0 N9 s break;; v0 N9 j% B1 N" @9 \
case 2:3 |6 H/ v+ V8 y
preresult -= Num;( x/ j2 k6 I, d' P0 b5 [
break;
I& n* I# E5 Q" {8 n case 3:8 ?7 }9 B0 X) \ I% ^ r3 @% B
preresult *= Num;
; y2 W! J- ^8 ^+ ]* i* @- j break;
0 C2 P2 W5 o$ ], s7 v b case 4:: y4 i$ Z% S+ W
if(Num == 0) return -1000;
! C) r1 M. C& Q$ i) _$ o ?: o( | preresult /= Num;" s. z$ H4 X+ S4 s, n' ^
break;3 ]* L/ L% t, Z/ M M2 |& \8 q6 u
}* w4 g; @3 R0 t" g" z
i++;j++;
) i3 F7 l8 m; a9 k% r }
% x; M" k1 P" c2 D* H3 O5 v return preresult; //进行修正
( A: B2 i9 I* g4 z }$ ?5 ?1 r3 j- s% e
// 打印算式
; U) Y1 g4 {# J0 g# [" w S2 ` void ShowFormula(int *Num,int *Sym,int count,int sum)8 G/ Q# `( U8 Z: k
{0 K. d. i6 K0 k3 m
% d( f/ z+ o4 O6 M( y. o0 t' M: S int i,j,len;
& W; M) Q7 q& N# E! _7 n8 k# ` char *Formula = (char*)calloc(count*4,sizeof(char));% T9 v, ^/ F' A% L& z
char temp[10];: Y8 E- n/ _9 ?7 c3 a
itoa(Num[0],Formula,10);
9 b/ G2 J, K0 l; k, }: f i=1;j=0;
( I* x5 w- J6 `3 T while(i+ O* Q: _2 Q6 K, c+ d" u {
7 b+ e0 S# {1 q) f8 R. [4 h itoa(Num,temp,10);. r: v. u' `6 t4 w
len = strlen(Formula);/ b! O7 X5 ?! Z- ~/ }( p$ R" S
switch(Sym[j])% y: a; y0 z& T
{* i! [# d' Y* H" Z4 v) n [' z
case 1:
, E4 T2 [/ J% O5 E case 2:
9 N+ S- ^7 l0 g/ i2 Q3 h/ E; F! Y Formula[len] = cSym[Sym[j]];
: v( j) W# B& Q0 a9 v( a+ G0 Y strcat(Formula,temp);3 A0 x, U: _2 V- H
break;$ ? a! z) J |2 D
case 3:5 K: E3 {9 D9 x" K
case 4: D. F. A/ e. C! o2 e% k/ V
( w% x3 A6 h/ g; r5 q0 C // 如果上一个操作符号优先级低于当前的，应加上括号' q+ F/ |) b. `5 V1 q6 n
if(j==0 || Sym[j-1] > 2)
4 `1 `' R+ @ f0 H- m& {* F1 S {
* i0 |; q, E& |" i Formula[len] = cSym[Sym[j]];! {% ~5 o9 j/ ^
strcat(Formula,temp);% @8 w* x# a. i! J* h
}* v U+ b1 s. a3 Z0 ]2 E- y
else
/ Y7 [: S8 _: K. c' Y/ L {5 O4 v2 [& I8 l& ~
int n;
; w8 ?9 h1 ~0 o5 k, U i/ v char *FormulaTemp = (char*)calloc(len+1,sizeof(char));5 [; J; h" O9 d* \& S7 G
for(n=0;n5 E5 G6 O3 x7 Q4 q5 a) ? {4 ?8 d) p3 s' l$ s- j- `
FormulaTemp[n] = Formula[n];" k# h2 F- n( ~
Formula[n] = 0;& K. N. s" P6 Z& C( T9 W/ _
}
o4 P( U3 [+ N" p/ p! C) g. M Formula[0] = '(';0 v% }. b8 @3 N* \4 {
strcat(Formula,FormulaTemp);8 V' E) A! A) q7 a( J8 h) F9 }
free(FormulaTemp);$ K( a0 r6 v6 g, ~5 Z
Formula[len+1] =')';& ~7 R/ s4 j9 k' n9 m, S1 R
Formula[len+2] = cSym[Sym[j]];) m3 G0 E, {$ N; r: G0 K
strcat(Formula,temp);
) s7 D1 I2 L( N8 e% y! t( Q }% f7 b" \4 @; y/ E; ~+ g
break;$ V) V' D" \ X$ q, A/ V# o
}
/ Y) s9 e0 w. Q$ ~% l2 `8 a i++;j++;2 R* @2 V! z1 n+ V; b: V/ T
}3 J) A9 d! K8 i7 f; V2 X
printf("%s",Formula);
: S8 ?/ d6 k1 S. a: ~* G printf("=%d\n",sum);
+ n9 l3 u# \3 F( m" D) p free(Formula);
^% \9 _6 M1 z3 d6 m/ S1 [1 C }( N4 t9 K: c+ ^% E
J( m7 O# ]6 A6 d; \+ K- @- N
// 以当前数组为基础得到一个从小到大排列的数组! p7 P5 |/ p; U/ M% w* N
// 返回非0表示穷举结束
# c" i' T! x- Q4 V2 H, G1 N int EnumArray(int *Num,int min,int max,int count), Q) D" r& ?+ c0 e% N9 C+ f [0 |
{
+ y9 a+ v1 s( M" c int i,top;/ W9 V5 x) G" c9 s+ f5 ]. s
top = count-1;
5 U% t! @8 J+ z/ y+ Y/ a Num[top]++;+ l- C% a: g: _$ `' B! }
while(Num[top]>max-count+top+1 && top>=0)
$ d' M+ S( C, K {8 S: `5 _% [# N5 o4 u& _
top--;4 Y3 Z9 e9 F7 C1 T- U& u
Num[top]++;. K- k1 f: n b+ r# R
}8 C5 ], D5 }8 R4 [$ q* y4 v9 E
for(i=top+1;i8 a+ Y% c) v$ z& e7 r
{
+ G9 U+ Q; Z6 m$ ? Num = Num[i-1]+1;& E. P% k1 R; T7 H1 T# [5 P
}4 U3 P! N/ D# ?' S* Y
if(Num[count-1] > max) return 1;+ w% x1 f9 w% n* Z B1 r9 x
else return 0;, U- B. Z7 Y3 d; L
}
# \& I* t/ L; U# b9 y2 Q B# s
& y! _5 @3 u7 n6 X& _2 b+ m) [7 } // 不允许重复的初始化数组
1 r& {6 P* M- j( b/ P void InitArray(int *Num,int min,int max,int count)
8 `- h( H# D' W" F: u {. i. N! w7 [0 C- \8 C! @( c8 L
int i;3 y: W V- ]6 _$ i: _( q8 v
for(i=0;i=min+i;' O4 w5 Q. j) r/ Z
Num[count-1]--;9 A4 T ]- E9 v. H* R1 ?' q
}
, i+ N9 J7 j$ ]0 X; L: X$ b* ]& B3 J) z) {, A7 q* V
9 q$ s& a# K8 |; X) ?/ ]4 l, r( N4 @7 T! R
2 t U2 j3 I4 ?! R( g7 } [此贴子已经被作者于2004-5-2 14:50:47编辑过] |
|
IP卡
狗仔卡
发表于 2004-4-27 17:53:00
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
分享
顶
踩
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
千斤顶
显身卡
发表于 2004-5-1 09:53:00
楼主
/1 
