TA的每日心情 | 奋斗
2015-9-17 00:58 |
|---|
签到天数: 1 天 [LV.1]初来乍到
|
以下是引用游侠无极限在2004-5-2 14:41:26的发言：
l# h6 e9 Q/ A) x#include
& s; F+ }0 ^4 l7 ]- H #include
' A- ?( v& Q- `6 w0 L) [' N
" {( l2 D/ b7 N3 G) X int EnumFormula(int min,int max,int num,int sum);! D$ f* ~; p8 v- c( R! w
void ShowFormula(int *Num,int *Sym,int count,int sum);9 H$ Q# y) v: `8 \1 |9 P. h" u: o
double GetFormulaVal(int *Num,int *Sym,int count);
. d0 A3 @7 a. | int EnumArray(int *Num,int min,int max,int count);
" w; k1 ~: l& T6 S void InitArray(int *Num,int min,int max,int count);& Q K% }+ N0 Z3 N
const char cSym[5] = {0,'+','-','*','/'}; ~* w5 w* e& L7 C
1 Z8 c% G. n6 P+ s
int main(int argc, char *argv[])
9 I2 T+ x4 y+ }2 z {
& j i3 }" M8 d2 x3 I/ C* y9 x printf("总计%d个式子\n",EnumFormula(1,10,4,24));
7 {& f: e/ w0 @1 J system(" AUSE");
% k! D8 a0 H7 [. }8 t return 0;
2 [: Q3 [, j4 v( J2 V3 H6 y }9 z& Z* j* W6 m8 D1 K9 z) v5 x
% u& }; j+ @; H% p. g- ]3 j int EnumFormula(int min,int max,int num,int sum) s6 P* h* D3 b, _2 q
{8 a1 j; @0 t* n- _$ @% Z
int *FormulaNum = (int*)calloc(num,sizeof(int)); //储存操作数( Z, `9 G* n: X! H3 S
//储存操作符号+ [1 X8 s a" g* B; b
//最后一位用于穷举结束标记
- n: ]* b/ |% [5 h3 H // 1 - 4 代表 '+' '-' '*' '/'& l' f. y% j; ^' P/ @/ i
int *FormulaSym = (int*)calloc(num,sizeof(int));
2 |' @3 c( G5 M& G* D
7 l" [6 _5 q+ L0 C int result = 0;
/ \- Q. M1 f7 X4 C" w/ `8 ~ // 初始化操作数和操作符号数组
! j0 o$ ~# L& \
9 T- V7 [1 ^0 B4 L, y, q int i;
. t c" D% |/ g9 c" o1 t- e: U9 u2 W0 _* E
for(i=0;i = min;
( p" W2 } t% V. i for(i=0;i = 1;1 Y F% b6 f7 w2 f, ~8 Q& I$ y
FormulaNum[0]--;
( U. T( |* [1 S H
. ?9 H, h* `1 E* H, ^/ |6 y4 L8 T InitArray(FormulaNum,min,max,num);
9 i4 f7 d$ W: C! C. ] x FormulaNum[num-1]++;
0 Z: S/ B/ Q( J/ U; l& L _( M% F // 穷举操作数和操作符号组合
, W8 D# W9 ~# K+ Q" c while(FormulaSym[num-1] == 1)4 O3 I) P4 ?1 A( ~: S5 m
{
" d$ Y! \) k: k4 |. e p0 ^ double t = GetFormulaVal(FormulaNum,FormulaSym,num) - sum;
% O7 J, W1 M. C* Y, W if(t>-0.01 && t<0.01)
% z2 u. U$ b4 H/ [ {
& h; D% p3 S, |: |# K5 C# r( C //printf("%d %d %d %d | %d %d %d ",FormulaNum[0],FormulaNum[1],
, a/ t* c- S+ S+ o- j% o; {0 n2 q //FormulaNum[2],FormulaNum[3],1 u2 }% G. V/ A {0 n6 l; X0 j
// FormulaSym[0],FormulaSym[1],
. H& J! B+ P9 q. |& l: c' n // FormulaSym[2],FormulaSym[3]);+ \! ^% w2 O1 n0 r: P
ShowFormula(FormulaNum,FormulaSym,num,sum);
3 w. X8 @9 v& |. U result++;0 Z1 Q/ B8 S* c
}4 v$ C8 L6 f- G3 E3 p7 L
/ T8 e1 O3 R5 g+ M7 x& ` // 依次穷举操作数
9 y, F U3 x1 b
) a/ x0 a8 N5 G) `" g* v //允许数字重复的穷举
6 }1 {( r. H& K3 t) ]* b8 d" ~& t //FormulaNum[0]++;8 T- l, l) v. P8 M& {, E6 x# N
//for(i=0;FormulaNum > max && i) H: u* G; s6 l( |
//{
# e! e$ T, w; W; Q/ _ // FormulaNum = min;
! |: {" E/ |# o$ {8 o- _6 Y9 z // FormulaNum[i+1]++;
+ s8 r7 t1 W; @" J3 r v //}
$ _; N& v M2 N, h( \; E // 操作数穷举与操作符号穷举联接
" j. p: X* j- a" N7 G //if(FormulaNum[num-1] > max)- S) K$ D: l" i0 n* h
//{. B# K. h$ ^, o
// FormulaNum[num-1] = min;
a3 G' ^% G m/ l" G3 A; G // FormulaSym[0]++;
2 _ y& j% \; c" h" Q3 q: v+ i7 [ //}+ q9 M% Y1 T9 [
2 R+ L( C V1 B5 J6 Z; G# e // 不允许数字重复的穷举2 {7 l3 d# N6 u: e0 ~
// 数字必须从小到大的排列，防止重复
: b1 P1 n6 V5 h4 z. `# t' \9 s" V( h if((max - min)< num) exit(0); // 出错
1 J- a3 J0 M/ v
" @1 Z) w4 P# U; l if(EnumArray(FormulaNum,min,max,num))
: ^5 D0 l( N5 o# C {5 L; [# q! ]+ j9 K
FormulaSym[0]++;" Y# V- Z4 b+ s3 L
InitArray(FormulaNum,min,max,num);
3 K/ ~& R, K: i: o- v5 l* |( w FormulaNum[num-1]++;
2 C" z1 D3 z9 H) X }
% [; M" K# y k
) l: d; E! K$ a' m3 N6 b // 操作符号穷举6 U6 u) O3 U: X, s1 _: |7 r- a; o
for(i=0;FormulaSym > 4 && i, K* X2 y! w; q/ B) q$ W6 U+ N- v- n+ {
{! Z9 G0 g% t; A
FormulaSym = 1;
9 c7 Q. s, d' i FormulaSym[i+1]++;
+ s8 Z0 i8 _2 p$ ]. F' @ }
( B [: P _! F
& p B: U5 F1 Z2 ?& {+ W) `$ l }
1 r, o x8 O @! S: [ E //释放空间
, t) `; D! P" u0 R4 v free(FormulaNum);
& g( `! y, G* h, h2 e( a/ V4 h free(FormulaSym);; x9 Y8 l. D" X) x' ]7 l$ H
return result;
$ P; R" w+ }4 K7 k4 I }: [- [: M0 K" T' U1 c4 T2 I
// 计算算式结果
2 C/ j* _0 `5 o$ |9 ?) R double GetFormulaVal(int *Num,int *Sym,int count) f8 Q1 W' l0 G+ O8 ~2 @
{
1 Z# ^! B7 @0 e7 \ int i,j;% X: ]2 p7 C/ ^. Y
double preresult;
* o) V" u- [" N* k1 O% I+ w preresult = Num[0];
, S7 Q8 d! R. [ i=1;j=0;
& `3 O b d; b$ F" d5 x; ^* H+ L while(i) s5 M9 w7 \2 t, q: g5 H7 s
{& H$ p7 s( z! ?; Z6 R
switch(Sym[j])5 R" K: N" D8 g* b# T. ~% z3 ~
{
6 V$ k F' J. Y# |9 R2 k* m* c case 1:
+ U5 K. T+ E9 ~1 K( j preresult += Num;& j) p$ z" m ~* K Z' I' J
break;; N. N, C2 V- Z- e- U8 }
case 2:
9 d. O2 F$ Y2 a v( Y preresult -= Num;6 a* f! _) W0 O& {7 ?* ?( c6 d
break;
# U$ z8 _0 @2 r! J) l! z z' o case 3:& n# w( u# I$ S8 r" G9 P; Q9 A& ?( ]
preresult *= Num;
+ S' L: X4 o" s2 K0 K break;
$ L6 F) v: Z( U/ a case 4:
' l1 ]; Y f$ U# c3 b+ F1 k if(Num == 0) return -1000;7 F2 ~* I( b7 y4 V
preresult /= Num;
& L! z4 R |5 Y F3 j$ L break;6 a3 J. P- U0 [# \! v
}
e0 ~! V% E5 A1 F: p i++;j++;
% T/ O. {3 M& d' S3 J }
p9 l0 @& N. p5 V4 c4 K6 k: E return preresult; //进行修正% L3 g/ Q6 k# ]+ ~0 n! C2 G
}
6 [! v% {0 Q) E: h( q3 n; \5 R // 打印算式( }* w( ?: q; l3 [9 U3 T- a, u" U
void ShowFormula(int *Num,int *Sym,int count,int sum)
# p: S# K: i6 g9 ~, B {
- ?9 G- b N8 ?+ e
. _: D r+ U& P/ d int i,j,len;# z8 S0 ^( _, D/ E- {- M
char *Formula = (char*)calloc(count*4,sizeof(char));
9 Y: [9 e! |4 Q. W; I q+ L char temp[10];& Z8 M3 {$ l6 Q$ R% H. V8 }
itoa(Num[0],Formula,10);5 ~+ |) c: | D. W3 J4 i7 {) t
i=1;j=0;
1 L8 t8 W, M" ]7 U" D: j while(i* \9 r/ p" C. f3 r. Z4 K
{
6 ^* S8 y4 `9 ^$ f itoa(Num,temp,10);& M" d, {/ G4 T( \9 T% S1 M
len = strlen(Formula);
( S. U! P5 b0 S% `% D9 X/ b7 ]) { switch(Sym[j])! Y/ I+ l9 p) \/ g& j+ J% `
{
! c+ F* }! @* M7 I$ [ case 1:
0 ^5 L& S% B, e5 z8 R case 2:' L& m$ n7 P6 B
Formula[len] = cSym[Sym[j]];1 j0 v3 n' `3 r% i, @2 ~
strcat(Formula,temp);
3 W( T* E. j- {# n* l0 q6 s6 g break;
, h3 s- @4 f; H7 l* \ case 3:2 ]/ I& H: f0 {# K" C/ m
case 4:. i* W8 B! [4 G
" h; o7 G& o0 e1 z3 ~; v6 U; U // 如果上一个操作符号优先级低于当前的，应加上括号
7 Q8 p/ [2 C6 @% [3 F' `8 r: ] if(j==0 || Sym[j-1] > 2)
; n# \6 H6 U2 t ~- x6 s {0 F6 X' u; Z5 |8 w
Formula[len] = cSym[Sym[j]];8 X* T/ Y$ i, }: b2 A
strcat(Formula,temp);: _0 |+ V6 J1 y' G x3 O
}4 V7 v8 s" C5 {9 O% V, N
else n" w" t9 h! y& A! ~
{
; E) y8 _0 q" G2 p* h; X6 e" R int n;
# d& p9 y* e$ ^( Q! Y9 Q3 e char *FormulaTemp = (char*)calloc(len+1,sizeof(char));
2 I! w0 e, ^5 s3 K for(n=0;n% E. ^% R8 C3 a' y3 C* c
{
[. w& c6 b/ a; x) d, D. K FormulaTemp[n] = Formula[n];
0 Q* W/ B0 Z0 M0 R3 M- @' C6 `1 T Formula[n] = 0;% T4 I6 j* Z& ~' U2 E& B# @
}
' y+ D5 {* x( `8 d p Formula[0] = '(';1 c4 G0 r- ^" \/ |8 ~- F, J. O/ ]% I
strcat(Formula,FormulaTemp);
- x: O5 F+ X% ~1 o8 c0 b free(FormulaTemp);# I9 _8 _2 w @; w( H+ j. d
Formula[len+1] =')';
8 T1 s0 i' |4 @5 V# _) S Formula[len+2] = cSym[Sym[j]];
: T Q( Y5 L$ I# a" R strcat(Formula,temp);) I( E8 m1 j, m. d8 @
}
7 Y. T5 X" L" {. U# C2 [0 J break;& r+ h% e8 T( ]9 ^3 d
}
* e7 {9 W7 b6 k8 I& q i++;j++;' L, z G- h9 \
} g" ]: B1 V" o( v
printf("%s",Formula);
f! H. `% \/ Z7 h4 \/ G printf("=%d\n",sum);
4 T. v: B, F) K w# j u( Z free(Formula);
) c$ A" w( |0 P, t }
# `( }& `; w6 |9 @) ^9 d2 A
; m9 n! P7 I# h2 t // 以当前数组为基础得到一个从小到大排列的数组; n9 k; ?. t) M4 h
// 返回非0表示穷举结束$ k. H# v5 [( ]0 a |
int EnumArray(int *Num,int min,int max,int count): [. T# L' g! j% @* Y# a
{
, I( j x) R1 @( C% [ int i,top;
7 t$ N) M( G- g top = count-1;8 m, O& e4 P b5 V1 @" g! I3 V
Num[top]++;# ?) g3 k' F) I# L9 k/ _' R
while(Num[top]>max-count+top+1 && top>=0)) s+ A" o3 l6 L; h0 g
{
+ A m5 N$ A! H0 I& }& u4 E top--;6 x4 n" e% _) F# @& c
Num[top]++;+ q/ o/ d% A( a, H
}
6 `% ]) n( E5 l8 j! w6 E for(i=top+1;i5 f0 z- }: a2 a {
: P# l' H3 [/ o# x; }: Z' M; _ Num = Num[i-1]+1;
+ Y; M2 h- K- Z4 r! ?: j) T$ F }
! Q$ Y6 w) |4 b5 o9 {6 d% u9 [ if(Num[count-1] > max) return 1;& H5 x5 r# v9 l4 J
else return 0;9 u& R6 ^8 C! ?: [: [
}
0 N. Y! f9 d( D% W8 r& A: D
, M) l! t7 Z* s" L; X p' O) C // 不允许重复的初始化数组
( o, E9 g! n2 @/ [1 d8 G: r void InitArray(int *Num,int min,int max,int count); D: ?/ g, E* w
{4 R9 d; D. n! j0 z" G
int i;4 ~' ]8 b3 p! Y, o& Z
for(i=0;i=min+i;
& C6 f. I4 Z$ J# |* T Num[count-1]--;
l8 W1 u4 M6 z3 ]3 d2 N }
: n: q8 [ `* ^$ b( p! W7 a( t
1 I% ~& S* ]4 k
( S8 n) P7 g c5 K+ G/ m7 W. s2 M6 u M+ b" G, G* E' F
' X" f* k {# Z' R3 v+ i# ` [此贴子已经被作者于2004-5-2 14:50:47编辑过] |
|
IP卡
狗仔卡
发表于 2004-4-27 17:53:00
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
分享
顶
踩
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
千斤顶
显身卡
发表于 2004-5-1 09:53:00
楼主
/1 
