TA的每日心情 | 奋斗
2015-9-17 00:58 |
|---|
签到天数: 1 天 [LV.1]初来乍到
|
以下是引用游侠无极限在2004-5-2 14:41:26的发言：( r" ?$ {/ R, j0 i5 Y
#include
2 n1 \3 ]( { m+ n #include
( o" {; F9 n- G9 l/ X: [; `; p
int EnumFormula(int min,int max,int num,int sum);. d# b, w1 k' Z3 |0 e
void ShowFormula(int *Num,int *Sym,int count,int sum);
- k& S* A+ F) K) P3 E9 h double GetFormulaVal(int *Num,int *Sym,int count);. I: u6 | Z6 w
int EnumArray(int *Num,int min,int max,int count);
2 D% O) [) F N( F; G! e+ N4 C+ Z void InitArray(int *Num,int min,int max,int count);
" R; X V0 a/ ` const char cSym[5] = {0,'+','-','*','/'};- a; A% D( A/ H7 B ]* ^) l
' m$ r/ k- E" `0 p( u, G
int main(int argc, char *argv[])
1 s; X# y( m8 N; ]: R {
2 W3 t+ i7 u8 N* d, k: l5 L' z printf("总计%d个式子\n",EnumFormula(1,10,4,24));! Z0 B3 Q% a1 l1 W: F
system(" AUSE"); " D9 v0 i. S' ]& R& l3 Y! o8 N
return 0;
$ D0 \; W. f- S, F5 c }
+ I+ j- O7 w. H' f5 R' q; h& ^! s% v/ s
int EnumFormula(int min,int max,int num,int sum)" K5 c9 U9 Q$ n$ [. A# Q* f' V
{/ z; g/ P$ [: q
int *FormulaNum = (int*)calloc(num,sizeof(int)); //储存操作数
: h& t% a( _" W2 D j //储存操作符号% ^5 C4 {# W, o1 F
//最后一位用于穷举结束标记
, h% y2 w# @" \, p, t1 ?) V // 1 - 4 代表 '+' '-' '*' '/'
+ d L4 ~& G n5 N' v int *FormulaSym = (int*)calloc(num,sizeof(int));
8 ^1 G8 u b9 c* B- B, _. U8 Q
+ X8 @ j0 N; H' y: l. O int result = 0;4 Y' d1 Q7 T% Z
// 初始化操作数和操作符号数组% t2 s9 N2 ]3 P- _2 G; v! C) k
$ y& d/ Z# i# g* w) h& y' x; ^
int i;
, { T! `2 [2 f# g. n- a Y
5 ^9 S; j) N: F' Z% B- `$ V6 q- | for(i=0;i = min;
$ s+ s+ [; c0 D9 D4 s/ {. [ for(i=0;i = 1;$ `& _7 P8 r+ g/ Q' A) D3 Q
FormulaNum[0]--;
$ E3 Y2 i- B0 t
1 f# I2 p2 b5 r' H y InitArray(FormulaNum,min,max,num);5 I% l6 v( h& O, S6 w
FormulaNum[num-1]++;
6 j$ w+ m. K3 I! P8 w$ \ // 穷举操作数和操作符号组合
, I+ S- c' m" C. a while(FormulaSym[num-1] == 1)
* ^, H8 |1 G- s) N8 Q {+ @6 x: _2 z7 }' a% }) l4 g- ]* _' N+ [
double t = GetFormulaVal(FormulaNum,FormulaSym,num) - sum;
3 W. e7 U4 {* j0 | if(t>-0.01 && t<0.01): a3 N( q# |* T6 P6 S
{
# _! a k* V" T" g: G/ Y) x& j# D //printf("%d %d %d %d | %d %d %d ",FormulaNum[0],FormulaNum[1],2 a) r' c& g% A" u
//FormulaNum[2],FormulaNum[3],- T; m* _5 N" p0 c, [
// FormulaSym[0],FormulaSym[1],, n7 i1 B' _. Y6 O! {
// FormulaSym[2],FormulaSym[3]);
( W4 s( D1 {6 X* @3 v4 G. C# ] ShowFormula(FormulaNum,FormulaSym,num,sum);
" z0 c. a; P' h5 P7 `5 F result++;
" D6 k' ` m& b4 s- z1 C }! C: @, C7 V1 x0 V9 ~% t
$ D0 s& o$ g* g8 Z
// 依次穷举操作数
5 o2 S8 s1 T; }0 x 4 _# J# G/ k# ^
//允许数字重复的穷举
) i6 f" p: c- \& c! z4 P7 a# B //FormulaNum[0]++;; z* [: F5 ?2 V2 T/ w0 J
//for(i=0;FormulaNum > max && i
6 s( l. j; W$ j2 E8 ]# G( f //{
5 F, R1 j/ f/ R* A0 U1 h, B- v* O+ v // FormulaNum = min;8 s; T/ ]; v/ Q: c! \
// FormulaNum[i+1]++;
% w( @" m% b1 r- ` //}
5 n& w# d: L4 I // 操作数穷举与操作符号穷举联接/ K/ y9 i0 ]& I# E5 c( v% }
//if(FormulaNum[num-1] > max)3 _5 Y7 S0 r) a8 m
//{
9 j/ z2 H& J" Z& P# E8 M // FormulaNum[num-1] = min;
# \# M" u. T; p3 ]% v, F. ?7 q# t C, U // FormulaSym[0]++;% y, j: l( r: ^6 v
//}3 {% D( L% D/ q
; P. E W- @( @# o9 g // 不允许数字重复的穷举3 T! M% X+ l' j, _
// 数字必须从小到大的排列，防止重复5 W6 R- F3 S3 ~ B, C; u
if((max - min)< num) exit(0); // 出错
" t$ n) g$ d' D( L' G
: o# R# l7 K/ I" k if(EnumArray(FormulaNum,min,max,num))
: u: F) H- G$ [8 A9 t4 x* K {
) f6 q7 C" [' g1 \4 W6 X FormulaSym[0]++;
" ^! x/ g2 |6 C5 `' A5 A InitArray(FormulaNum,min,max,num);0 y( s: S: `1 v* R6 R! _; w; t
FormulaNum[num-1]++;
( s3 G3 w* M }! u- S }$ J( ^, O! s* c
; W. I; S' M; ]% Z3 j5 P3 L) L& z
// 操作符号穷举2 w h4 ?! n" }4 I
for(i=0;FormulaSym > 4 && i" t% J6 {: ^7 t: G- d) | {
. K" k8 P. _3 n0 y/ i# H0 u3 ` FormulaSym = 1;
7 M v7 E$ a( s% e1 j. h8 @" p& { FormulaSym[i+1]++;
8 q$ f0 v# B3 e: Z. b" U+ m4 T' O }
% {9 k# B6 Q$ M. _5 D7 T0 Y+ _) z8 f A% \+ n0 [/ v: e
}( a; ~" t+ M& t7 u9 S
//释放空间/ [# W" d; N( c
free(FormulaNum);- F4 b2 p3 E' w9 b# T0 [; i
free(FormulaSym);
, ?6 i; ]5 O h5 r" h/ F$ p" J return result;/ @2 J; i8 B+ Z- H7 c% d
} U" T( o& E ]( Y0 t) R' j
// 计算算式结果# S/ a; y; h5 N6 }8 E
double GetFormulaVal(int *Num,int *Sym,int count)
H' H# }6 \+ a. s+ b3 y% T: K1 r3 ^ {- b; u* o* s: F
int i,j;
% e$ v# `4 @7 ~' N: p7 A9 r9 @/ p! Y double preresult;
: N8 g1 E& B9 m( o( } preresult = Num[0];
0 O! X3 \; J8 w: ?0 }3 |3 l i=1;j=0;* q" f* ] \2 R! J
while(i# f3 B6 ?/ m9 [" _+ V {
- a- r* W3 ~. a2 t6 p/ { switch(Sym[j])% C; Y. h7 R5 K! @6 A# m
{
- F0 @0 Y' i) s% d5 A U0 U, B M case 1:8 S6 D' t+ `$ z& k
preresult += Num;$ ?+ b# _* g. I7 `
break;, Z6 g' I5 G5 }% V( `
case 2:* m2 N4 T9 \# S: X4 p
preresult -= Num;9 f' j4 b) f" @& S& Y
break;
4 E- f8 r s' v9 U! u, e case 3:, Q1 @- \2 N @
preresult *= Num;! [1 L$ o6 N: m$ w+ k8 A7 X( N4 k2 c' B
break;
; o% F4 f# B* K5 D* M D case 4:- {, E6 a+ B8 \7 ?! i
if(Num == 0) return -1000;. R* w6 p$ f& R G
preresult /= Num; _: v4 u# m0 |8 j
break;
% T- V; s% ^* x }
- Y* d/ M$ ^! R( P6 i i++;j++;
3 s# b3 O: Z* i" [ }
) T, I8 ?( F. m) G4 U3 n- } return preresult; //进行修正 T* E2 N9 q. q) w R
}
$ R. x9 ^ m! y1 ~+ h // 打印算式7 B' K; ^0 i6 g7 w
void ShowFormula(int *Num,int *Sym,int count,int sum)
+ W1 w4 |0 G2 ^* |9 s {
/ j3 b- g2 S; B7 |# i6 B% E) X
5 W0 Y9 H( p. r* A. [ int i,j,len;
( ^! `7 A; G/ f2 |) } char *Formula = (char*)calloc(count*4,sizeof(char));
1 A! w* H3 a/ y: s% D# H) I: V# D- z char temp[10];
1 T+ y( l( O+ ] itoa(Num[0],Formula,10);
" n7 [1 s- b; |7 p7 T9 L i=1;j=0;
- T( |; @" D8 Q while(i; S ?, F1 O0 z {
9 [1 g1 M `" q. m6 B itoa(Num,temp,10);
5 F4 f" k. z( j0 h+ u N! F! `6 h len = strlen(Formula);
+ D# p2 u/ j1 [ switch(Sym[j])
: j+ W: U$ a( Q% L+ p {: \. h% S- P1 M# s
case 1:8 c" d$ ?# Q2 f$ H
case 2:
; o7 S, ]9 R6 l/ @! L Formula[len] = cSym[Sym[j]];
B' W( W8 O9 p5 z' D3 e" l$ @ strcat(Formula,temp);* Q% [" \# @9 }1 F. C+ w. b+ q
break;
; _, B" X! ?; T1 v4 { A. E, v case 3:, e5 ~2 w- o; h
case 4:
* m0 j6 t' ~0 R* x; i% O# k
6 ^+ i* B4 J6 I! J( j // 如果上一个操作符号优先级低于当前的，应加上括号) v e% Y3 L; o2 `: g
if(j==0 || Sym[j-1] > 2)
/ Y, e$ t5 v# Q' {5 X4 N {
0 b; I6 ^+ m, _% O! F6 f! c$ a# k% f Formula[len] = cSym[Sym[j]];
: c. R, c% n q4 _" G% U strcat(Formula,temp);
4 t6 A' O" J" z- } }
1 G( f' Q- q" H else
: A* Y5 D( x# W- Q {
. S: K4 b) s+ _7 w- x3 J0 q" V4 `6 L int n;- o* o O1 H' j* x
char *FormulaTemp = (char*)calloc(len+1,sizeof(char));
" ~" O8 z/ x# L, \( i- ?$ ^ for(n=0;n Z% v) u2 Z. g6 ?; i& P/ Q {
) [9 c3 ]5 d3 H5 c6 R! v. }6 N( Y FormulaTemp[n] = Formula[n];) _: ]6 b5 N# r0 ]3 w/ F# E
Formula[n] = 0;4 F+ A9 K5 n0 w; s6 k# v3 ~$ O
}
: ?$ p+ {9 X4 e" I: Z& K( i Formula[0] = '(';, {! P* {6 N" ?0 S' ~
strcat(Formula,FormulaTemp);) f) {, h- m/ q8 S; n1 E6 D
free(FormulaTemp);0 j+ n( q& h% [8 Z7 b
Formula[len+1] =')';
3 A: J9 f% f, h6 ?" v8 L3 h Formula[len+2] = cSym[Sym[j]];4 e- R" p, G# b1 _3 G* p
strcat(Formula,temp);# c. ~2 z: z/ x7 V" m5 D0 g, u
}
7 c* z, C+ _2 I7 N! {& a7 j break;2 K# t9 F* j$ [. d/ Z. Y# p+ a
}
' i) Y1 o" D3 C# [9 E7 s, y$ D; N i++;j++;
* s" i' O* w% J) {/ A }
( n* z2 w& ^$ @+ l printf("%s",Formula);& D1 a/ R1 f( d& d& Q
printf("=%d\n",sum);
# t* }! T p2 j" i* F* |/ E6 w) U4 { free(Formula);
7 l; J% o1 l5 F+ D Y' c }9 ]( x, {$ ]' }; `
5 q' m5 p! O v/ X# w, v$ ~
// 以当前数组为基础得到一个从小到大排列的数组$ k( V. ^6 }% u) z
// 返回非0表示穷举结束
, ]$ |9 A$ w) c3 _. Y8 R int EnumArray(int *Num,int min,int max,int count)- I5 p0 k! U8 B2 z
{! V& W4 E1 l# D4 m; K; B
int i,top;
" d1 O4 t K6 Z/ z6 V top = count-1;+ O) n) x+ y A) P1 |/ u2 F: ]& G
Num[top]++;# v( m6 O y; I; P& ~) ]
while(Num[top]>max-count+top+1 && top>=0)
' g2 x- C6 R i. x; Q) p+ O {
& h' _* S; ?# f5 h2 N& u top--;
( g- ]/ w e! V3 n+ H4 C Num[top]++;
9 b* Y! z; z* n E8 ] }2 x; c4 l# j9 Y
for(i=top+1;i j. K. f. r5 H+ O4 K {
# }5 j7 k" U8 U) D5 b" j: A; H. w0 K Num = Num[i-1]+1;% M) Y. Y) [. x9 T$ E: G
}
( _" E7 G; L! M! m3 G: M) R2 s* ^: O if(Num[count-1] > max) return 1;
. J X" C5 o2 `3 G8 j' s1 N; Y2 s. m else return 0;! ^$ H7 i+ M. @0 v0 P
}8 y- U' [6 y0 P
( x! ^" W% z$ h# n5 K. s // 不允许重复的初始化数组
) n9 V# Y8 X, C/ N9 e2 O, W void InitArray(int *Num,int min,int max,int count)# x6 `% M+ X& y( f; ~ K
{
3 u8 j Z* I* Z# l int i;5 `0 r0 j9 m* a; U) f
for(i=0;i=min+i;
, S8 K6 m/ [5 o0 j: Z" Y Num[count-1]--;% M+ o( B8 z, C
}* y3 F) G3 Z$ G% w8 s
, R+ u3 p1 g5 y
% Q) E+ S$ S6 Q- k. H) b, z5 B+ e# _1 Y5 G+ N
s( E( J8 _# C7 U7 A [此贴子已经被作者于2004-5-2 14:50:47编辑过] |
|
IP卡
狗仔卡
发表于 2004-4-27 17:53:00
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
分享
顶
踩
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
千斤顶
显身卡
发表于 2004-5-1 09:53:00
楼主
/1 
