TA的每日心情 | 奋斗
2015-9-17 00:58 |
|---|
签到天数: 1 天 [LV.1]初来乍到
|
以下是引用游侠无极限在2004-5-2 14:41:26的发言：
9 j" E; m" V' H' ?4 ^#include + P" {3 \5 l7 G) M
#include
) i- q, C& ^2 p4 s; W+ Q. K" R
1 @& E' J$ w0 _ int EnumFormula(int min,int max,int num,int sum);; L4 P2 f: j( z3 J) P1 ]6 Q
void ShowFormula(int *Num,int *Sym,int count,int sum);
6 T" K7 ~2 y1 I; f2 F double GetFormulaVal(int *Num,int *Sym,int count);
+ m" o9 E U) X3 g int EnumArray(int *Num,int min,int max,int count);
0 q h% f/ @3 G8 u: B1 V' z8 v' F void InitArray(int *Num,int min,int max,int count);2 a, s$ ^0 U3 ]' V4 i
const char cSym[5] = {0,'+','-','*','/'};8 G$ M, Y. e8 W, ~
+ o4 E$ j7 E3 w
int main(int argc, char *argv[])
3 K9 v \- {9 j0 P' G) x2 } { B! M" G% x; K3 @
printf("总计%d个式子\n",EnumFormula(1,10,4,24));& Q" \( [. z6 ?
system(" AUSE"); / _$ }( ~4 ~! p5 r* l- u1 k# i
return 0;
/ f$ y+ Q; X! O- T8 h }; J' u5 b: E' _! K6 r
5 f; @! L% @# G% w. g' o, a- C5 j
int EnumFormula(int min,int max,int num,int sum)
2 Z) |1 }8 y$ P+ S( G {0 x4 e% g" } G0 V; x# K& h+ e7 s
int *FormulaNum = (int*)calloc(num,sizeof(int)); //储存操作数
$ c. @+ ?3 ~/ L4 ?; V //储存操作符号
4 Z& f/ l" z/ O+ l% G j //最后一位用于穷举结束标记
7 I3 ?/ x- k% f+ {& S( z // 1 - 4 代表 '+' '-' '*' '/'4 O7 Y) x3 d* V9 B5 z
int *FormulaSym = (int*)calloc(num,sizeof(int));* l2 E( j$ v; [3 q& H/ v
7 y$ h- d2 S6 W5 i5 u! Z int result = 0;2 B; {7 i& B& b: K" c
// 初始化操作数和操作符号数组
$ ]' Q1 m0 D' [4 P, f; R. n
" |- \" H0 R3 H int i;+ J! o8 z& E% Y6 B8 c* s" |. _
- y$ }# }& D+ S3 v for(i=0;i = min;' l1 l. N/ D. O# J. t
for(i=0;i = 1;- d7 D% Q/ ]3 P+ O& d, M4 O" e
FormulaNum[0]--;
0 W1 I4 S4 C. u( s/ K8 H' k+ v9 u1 I6 G) O
InitArray(FormulaNum,min,max,num);/ r% m {& \- g* v5 S" @) i @
FormulaNum[num-1]++;
4 T, P) o, X, G L" q6 \. y // 穷举操作数和操作符号组合5 g! r9 Z! N/ `( I
while(FormulaSym[num-1] == 1)
/ W- q, ^; f9 o% R {
7 z& e, {# ]1 T% O7 j( v4 T* O& J double t = GetFormulaVal(FormulaNum,FormulaSym,num) - sum;; D8 O; w, B4 L0 P# ~
if(t>-0.01 && t<0.01)
K2 c% S9 i& [9 b( k8 f" B# x$ b {+ ~6 _* W G) k- X/ a3 i
//printf("%d %d %d %d | %d %d %d ",FormulaNum[0],FormulaNum[1],
7 B$ t9 l5 N1 ?. L //FormulaNum[2],FormulaNum[3],$ w+ W. c) i1 n* i7 y: K: N
// FormulaSym[0],FormulaSym[1],
" s8 M, [+ @% M7 I // FormulaSym[2],FormulaSym[3]);" ?* \$ V9 b6 i! f. `9 e
ShowFormula(FormulaNum,FormulaSym,num,sum);
/ T1 X' m( i. K N/ n result++;
9 z9 `5 w% e9 n! ^7 g) S, c S }
/ W; F) {2 h& m/ A: r- W8 o4 O " h1 W# P: s d5 d' `$ [& W1 V; X
// 依次穷举操作数' r" m5 N- M: x2 W1 U
1 Z0 D/ A" E) O( w# k //允许数字重复的穷举
. i! I0 h! O3 n+ I; ^! F //FormulaNum[0]++;: _8 M9 f1 p' b. O
//for(i=0;FormulaNum > max && i
+ \; g; N7 h/ F; D1 n$ ` //{
6 q: U6 J9 D5 N& s // FormulaNum = min;- b- {" u4 d' U# A
// FormulaNum[i+1]++;
" m" u. _4 g. E$ n% u- N //}
s9 n- x" h% [1 Y2 v // 操作数穷举与操作符号穷举联接* j% x! P& w, P. A, r# ?' ?6 J
//if(FormulaNum[num-1] > max)
. M* O! ?* |! I- K5 e7 L //{
5 I. g T) Z ^3 i# @4 i // FormulaNum[num-1] = min;
* S1 _) C; @- X, z // FormulaSym[0]++;
( |0 X" m8 `+ M; f9 { //}
$ ]( n& F( G. R3 p f( Y; l
) Q$ M' |! B3 E" A // 不允许数字重复的穷举8 A9 [1 t, I) E2 l7 S Z% r
// 数字必须从小到大的排列，防止重复, O$ U2 I( L# O' s. N2 r; Z
if((max - min)< num) exit(0); // 出错; V! U; z4 k0 W6 N) b, G
7 U% B7 E6 `. k
if(EnumArray(FormulaNum,min,max,num)): N/ @1 \( m& T
{. P) b/ O: ?) k& W
FormulaSym[0]++;
* q, p3 { H; P1 O- J' d InitArray(FormulaNum,min,max,num);& y0 m J, _# A
FormulaNum[num-1]++;; F/ l& x" J. j, S
}
Q( a. G8 H; w; M+ Q # W' B' f) M( \9 H+ z
// 操作符号穷举0 r4 ^! `! I4 j
for(i=0;FormulaSym > 4 && i" @2 Z* ^3 P8 j7 V* u {' ]- O) I* n! i/ A) @" T
FormulaSym = 1;
) ~+ W) C4 I# T' t/ O FormulaSym[i+1]++;
% v) h& E; O6 {5 }6 a }9 @: F+ x3 |3 T+ D$ \5 H4 [
) @9 A; R: B9 [
}
6 T2 `, N5 n4 ]8 y: t3 ] //释放空间
/ k4 f8 X' n! ^. C4 W free(FormulaNum);4 w: G( p |( J+ p
free(FormulaSym);! z- ~5 Z" t) O) q2 e* R
return result;; {. \( g& `8 d3 S
}
% N7 S; c( T) N$ P* y+ `' ^3 \: d // 计算算式结果
3 x0 n: x2 H! K4 m7 c: q double GetFormulaVal(int *Num,int *Sym,int count)# f# d& Z# L. Y: j+ R, ~
{7 P; a, v- R" T; o' m3 d3 n, G
int i,j;" x' K( U/ x; S
double preresult;1 k- Y* A& L0 Y& v( D" Y* T+ \7 c/ Z
preresult = Num[0];
* I8 o3 I' _$ A% m8 t i=1;j=0;8 w" ?1 w) X/ U. H1 r x8 @5 a( u
while(i/ n" S; \: h2 v, L {
; o4 }& [% ^$ f n# f1 H switch(Sym[j])% o! C" K9 V2 W( U+ S# V
{
$ ~( b3 g$ e0 w case 1:
% ?6 c5 }5 E1 a2 n; g6 y preresult += Num;
! y3 V3 L- H0 L- T/ C break;
# h1 F7 h3 U! k5 O* }' [ case 2:* V- ~% c$ J/ [4 B+ {' _
preresult -= Num;
# q3 h! J. [* e0 N0 _9 V5 Y break;* k( `0 L- |( t1 ] i3 b5 X
case 3:
& o- x1 y. j2 ^ preresult *= Num;
4 `( s) _7 X) R; g! u% E break;
( x0 h; v1 ~( } case 4: `4 l' y6 N. }) B
if(Num == 0) return -1000;
7 R }8 D' R5 x: T, k preresult /= Num;
9 C7 t5 s! ^& _: ~3 Z break;
7 V/ l* w6 H% R" j! L3 K+ B }
) w. }: O* f# ~0 i i++;j++;
$ Q3 f1 t9 d+ U0 Y" w0 `- W0 j }
5 I9 ?, M$ c9 {3 B1 p5 U3 ] return preresult; //进行修正
9 D" I I J7 B$ k+ z: r, o }
8 J* {( D5 U( p) s G5 h // 打印算式
8 [# g8 @% G4 n4 n void ShowFormula(int *Num,int *Sym,int count,int sum)7 x, `& q% w4 z+ V l/ u( i
{
3 f# N" X. T; r1 |# R
- i4 g7 {) `; O2 L$ o int i,j,len;1 u) y! ^) K4 U
char *Formula = (char*)calloc(count*4,sizeof(char));
& P2 l; Z3 ^6 h8 s- T2 C; q char temp[10];: I' T* d+ i6 i
itoa(Num[0],Formula,10);9 j# O9 _" @/ A6 e! ^
i=1;j=0;7 I& g. G2 C4 z1 w1 \
while(i0 n: [* Z% Y4 w: \5 T) N
{
. L$ n1 T1 w8 S. g! k* ~- R5 |8 ^ itoa(Num,temp,10);
5 @; p; |+ h- n0 }+ D* w len = strlen(Formula);
. v; y1 H5 X/ g0 N switch(Sym[j])' e" W: T- x3 P; [/ b2 P
{2 k+ t+ k# C4 k2 I' U1 \
case 1:
" n* I+ ?1 s. M4 G, x case 2:4 U5 f6 k3 v3 U
Formula[len] = cSym[Sym[j]];
4 t6 t/ V& m, ]. h' I! N/ |* [& F strcat(Formula,temp);
$ _* {2 p) }% Z6 s break;
5 `& D# m$ T9 ^1 Y3 } case 3:
]" {* y$ p6 u5 N$ k G* h+ x2 m case 4:- M# D& u7 v7 P' q/ @, }
* e) j) X5 K3 _) s# l$ |/ N( |) { // 如果上一个操作符号优先级低于当前的，应加上括号
X! ^5 k9 Z5 v0 \# E* m if(j==0 || Sym[j-1] > 2)
u y$ J' r$ | {3 T2 Q/ i5 u$ m+ M0 a( Z
Formula[len] = cSym[Sym[j]];
7 i5 A7 N t; a/ d+ B strcat(Formula,temp);$ q( E" l: m+ m3 p" H1 [, w
}
1 p E8 _4 a4 u4 o$ L5 J! ^ else
4 @0 I" D5 `0 X1 i {' f- n# X3 ~% S/ o- e0 X
int n;
0 y4 w( |0 N# S8 ? char *FormulaTemp = (char*)calloc(len+1,sizeof(char));
: n9 p) {% F) T. r" x5 [, U. u for(n=0;n0 `! f+ u6 ~4 Z/ U2 {. e! I% `
{
/ s) y) W9 G. f3 `4 L& j FormulaTemp[n] = Formula[n];: l2 _& h5 ^1 }6 W3 U
Formula[n] = 0;( T" |, [. y8 a0 ]) S
}
, t! S5 A, W8 L' s. c" Q' }; c7 M$ D+ e Formula[0] = '(';$ |' u- |" O' J9 X9 l/ ]
strcat(Formula,FormulaTemp);1 L- L1 B; k9 a: t/ U
free(FormulaTemp);
% ]0 O0 s% K [+ u- H) [( j9 t" k Formula[len+1] =')';! T0 u! y, D5 ?9 s y( y3 \& V% q
Formula[len+2] = cSym[Sym[j]];/ u9 e7 K7 |0 ]
strcat(Formula,temp);
. }" v$ d5 d, k+ b }! p2 K. ^0 R% G' S3 x0 g: Q' \
break;7 K4 D% w) ?/ ]% ]
}
2 I j9 y8 a2 Z) k/ h) J i++;j++;
8 s H* ^0 J; b5 M" P' h }& n m2 B% W" O8 B
printf("%s",Formula);9 h- k9 p$ o& i) h( L; ]
printf("=%d\n",sum);
9 b: D% W7 Y- y! ?) K free(Formula);
( Q4 r1 `! w! [3 ~: V8 F* [ }
3 a; G) b* L( p9 y S, o* R
$ |9 q) {" R9 f8 {9 m) G% s // 以当前数组为基础得到一个从小到大排列的数组
5 U7 [( l6 p& B. N- c // 返回非0表示穷举结束/ e) n! [3 [( h/ n7 @
int EnumArray(int *Num,int min,int max,int count)
9 D4 Y; m, G$ r5 n. o+ t ?! M {
- n" z' ]5 l- f* s: |4 z int i,top;* n9 v, r* @3 d# C# b9 q
top = count-1;; Q/ f2 B. ~, H# Q- {
Num[top]++;
( x, Y) x- z& B( u while(Num[top]>max-count+top+1 && top>=0)
5 M+ P* {* c `7 W& I {0 T O+ j/ P4 A q- W! k
top--;& ^4 }- A9 A7 N! w
Num[top]++;
% j1 s. s5 J% J8 J' y) y7 a F3 b }& r: J- t2 ~: T( J; q
for(i=top+1;i( R* i1 Z+ x# ^; t4 Q, C* H {
. E4 B) `5 @: v$ {2 O+ r; s; m Num = Num[i-1]+1;! r0 q# L- A! x9 u" p$ F- M- Z
}# p0 x" @# j/ @7 h) @
if(Num[count-1] > max) return 1;& F. N! g. Y9 I
else return 0;
/ ?( h$ a4 F4 Y+ q' m- J) n }4 E; C* k" q- z8 q& m
2 f3 b& @$ D! e- L( S/ u
// 不允许重复的初始化数组
0 D* q6 h! r/ x1 i- b: y; R; [ void InitArray(int *Num,int min,int max,int count)
' ^( ?; M' Y0 Q) a9 K9 g {
) x1 U$ ~- C8 g: p) }8 O! ]( L# w& g int i;
$ R5 l; n5 G; D7 U3 t9 @/ y4 c) { for(i=0;i=min+i;! K" `- p9 L6 ?* R9 k$ ~% w. u
Num[count-1]--;
4 F) Z% b3 H5 q; j }
3 [0 N, b/ S- O
& e( h) e, H5 q/ n$ x 5 M+ G v9 h$ f. n4 V2 G7 {
8 y: L" N1 Y- `/ I
1 S) K! T) w4 B3 @, | i [此贴子已经被作者于2004-5-2 14:50:47编辑过] |
|
IP卡
狗仔卡
发表于 2004-4-27 17:53:00
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
分享
顶
踩
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
千斤顶
显身卡
发表于 2004-5-1 09:53:00
楼主
/1 
