TA的每日心情 | 奋斗
2015-9-17 00:58 |
|---|
签到天数: 1 天 [LV.1]初来乍到
|
以下是引用游侠无极限在2004-5-2 14:41:26的发言：7 e9 B2 P% r, Z6 \0 h
#include N# B/ t( [) ?: G: c) |
#include 2 Y% o( ^- x8 I) ^
* P- [* v5 Y" o; @ Y int EnumFormula(int min,int max,int num,int sum);
$ s: _; W- }. y0 f' U4 [- l! _* T void ShowFormula(int *Num,int *Sym,int count,int sum);$ X6 W% n) ?7 ?, }5 j/ [( V
double GetFormulaVal(int *Num,int *Sym,int count);
t3 o: z3 M" V8 ^# Q8 a int EnumArray(int *Num,int min,int max,int count);
# n0 E; `0 }* A& }0 n1 j void InitArray(int *Num,int min,int max,int count);5 Q, n& y. q6 K% s1 ?; @# Q) T5 c
const char cSym[5] = {0,'+','-','*','/'};
% X% u( j8 M& l7 _4 M' X8 z! G
int main(int argc, char *argv[]); m& r; W: h" g' R6 i( e6 C9 `% Z
{
6 T1 u1 W7 M( |; B3 E/ O2 S printf("总计%d个式子\n",EnumFormula(1,10,4,24));+ S1 V4 Y+ j9 W/ b# `% @5 B% y
system(" AUSE"); 3 ?8 b. D! t; c: M" b( b2 L; P
return 0;
% r( z# S- N/ d$ F% o4 }, W$ p& M }9 t8 p% m$ ]8 F) w
, u2 h5 ~8 ]+ Y v5 c, W4 t N7 A
int EnumFormula(int min,int max,int num,int sum)
& b" M2 W$ ~. N$ N& K% l. w {1 D7 n, p* ]: C. j; a" C
int *FormulaNum = (int*)calloc(num,sizeof(int)); //储存操作数9 O( z& g5 u+ N9 a* S
//储存操作符号6 a1 Y( E( v5 D6 F) b
//最后一位用于穷举结束标记
( c( I$ q3 e% P3 a // 1 - 4 代表 '+' '-' '*' '/'
% y; ?" c5 \0 G: o- p int *FormulaSym = (int*)calloc(num,sizeof(int)); O$ Q" O @1 R+ h3 r- B
+ g4 @$ \: t9 O/ B* { int result = 0;
$ V5 g, t( F: Z" \0 k) S' y1 i$ v // 初始化操作数和操作符号数组
0 c* ~6 h4 q# \/ R % m" j; Z4 [* ?6 R J
int i;
" ?" \1 n# I4 k
" d+ G0 k2 f- m9 u* E! z for(i=0;i = min;. M: p/ V4 |0 }9 O
for(i=0;i = 1;8 l; {" q! E! l' X6 i
FormulaNum[0]--;
/ M6 m6 _/ l1 w: F4 y) z, }* f! d# N0 q3 B* {$ @- i4 x
InitArray(FormulaNum,min,max,num);
- b# M2 }+ s! x. k- |' q FormulaNum[num-1]++;
( a! [4 H, F% v9 `% V) J // 穷举操作数和操作符号组合
& z f; @' S K h9 O+ Z while(FormulaSym[num-1] == 1)
6 C& E+ m F: o4 z( t/ B1 U2 u) \ {
1 z; |. u6 q( h2 A! K: O double t = GetFormulaVal(FormulaNum,FormulaSym,num) - sum;
4 Y6 t4 c4 D. y0 i) e8 N if(t>-0.01 && t<0.01)
" E1 w8 |# F" v# M {) m6 w" Q" k1 W( U& J
//printf("%d %d %d %d | %d %d %d ",FormulaNum[0],FormulaNum[1],
$ L; k9 J8 h4 S' Z N" Q9 j: }' F //FormulaNum[2],FormulaNum[3],5 U3 _5 l/ J; m. }6 N: s5 p
// FormulaSym[0],FormulaSym[1],
* f* b" p7 |/ B% w2 O // FormulaSym[2],FormulaSym[3]);- Z; M+ y* B3 Q2 f% K& D4 T* u3 `
ShowFormula(FormulaNum,FormulaSym,num,sum);2 D$ v1 j8 p9 e- L/ K
result++;0 c# A! z4 S) N/ y
}
9 i$ D# X, r% ] R+ x
2 A% ?0 N% v$ U( I9 S // 依次穷举操作数
( O% ]. u4 N$ X4 z' S ; C, ]6 I/ Z6 \0 N
//允许数字重复的穷举
5 w6 l8 g, x! [* z //FormulaNum[0]++;
2 b$ l0 \4 |5 E9 f, Q# ^, D4 ^: Y //for(i=0;FormulaNum > max && i
5 ^* I2 U9 `1 y O7 ]8 b //{
0 Z [" d! e# g7 g f // FormulaNum = min;+ A7 x( J6 Q8 z0 \; S
// FormulaNum[i+1]++;# _3 V1 K f- x4 ^
//}5 m1 }9 M4 z) I5 ?( ~) B* S- r. k
// 操作数穷举与操作符号穷举联接
/ \8 S5 e) ~! B( P4 R //if(FormulaNum[num-1] > max)$ p- l& a; Y) w- _+ f: M
//{$ C9 C. ~( R0 M- d; R
// FormulaNum[num-1] = min;! `5 `- e; s" E6 R. y
// FormulaSym[0]++;' D* A3 e- X T, \$ [6 \
//}
, Y9 Q R& u' y/ d
& \! x+ a5 |1 O0 L5 g2 h // 不允许数字重复的穷举
9 e* r- N; X& x" P+ j( w4 w' R8 U6 ~ // 数字必须从小到大的排列，防止重复" H' w/ e( _0 q) w" [. b! e
if((max - min)< num) exit(0); // 出错% A/ n( G) k" p; s' ]9 ^! `5 f
4 k& }8 E+ y( N
if(EnumArray(FormulaNum,min,max,num))
8 v' a; E2 l3 Q. ^* I; k( ~ {# G; Z8 Q. ^5 \9 Y3 g! |
FormulaSym[0]++;( G, O8 v. }, t3 B* y& a
InitArray(FormulaNum,min,max,num);
7 u/ _" r' K" B ]& E% ]) U7 ? FormulaNum[num-1]++;: S n8 T- }' W" h$ ]1 D6 A
}- |3 Y; X9 m9 u7 H0 W! s
6 ?1 r; R6 u9 a G$ h1 x
// 操作符号穷举
# X3 f' j7 w' o% T& G8 Q for(i=0;FormulaSym > 4 && i: k& Y6 B. |" o$ P2 g {/ u) ~/ S3 ]% E
FormulaSym = 1;
/ F( a! L; [& T$ P2 q FormulaSym[i+1]++;0 j+ R& ?3 J; `6 r" ^ I
}
8 l9 X1 k5 i3 s: f* U7 }& r1 B" b
}+ b' B! P. m% ?$ |
//释放空间
* N4 t8 O& \ z' \ free(FormulaNum);
. t( Y* N; C$ S: p. e$ a free(FormulaSym);# y: T+ D5 N9 Z S0 t5 c
return result;
! M5 n6 d* x# {, p( e& l }7 ?; Q$ `# l: y* }9 V3 |( d9 E
// 计算算式结果
' e4 u6 [& p0 R4 p$ w( l4 e; r double GetFormulaVal(int *Num,int *Sym,int count)
9 V7 h, z/ D& b* U u% W& y {
+ M ^* l" `9 Z6 ^6 B int i,j;8 T! y+ b- o' ^
double preresult;
0 {3 I' |0 P$ S preresult = Num[0];
! r' U0 M6 k) X& e4 z8 `6 t i=1;j=0;
. L2 X I( c* ?4 ^( l while(i8 b& \1 C0 z& O. Q3 s& d
{
3 l9 J. @. l; m: b1 U& n$ a4 ~ switch(Sym[j]). D8 g6 K$ k' {
{) `1 j1 J( J" m( Q( W$ U% O6 X
case 1:# j8 v" {6 [9 t! {, R. z
preresult += Num;' |: j( L" e* r* a- N
break;# @# s+ H+ |" d: m
case 2:
: @" Z- ]7 }" \& P$ }) A preresult -= Num;$ [6 w2 R5 T |2 v6 B2 K
break;. m8 J" M: r3 f) A: C- l
case 3:- a9 @% c! J; a5 V
preresult *= Num;
9 Q( L- h& D! {$ Z* z break;
2 j, R; v" I0 q; d case 4:
, k3 f" T7 N7 j' Q }1 G6 q5 P if(Num == 0) return -1000;0 S6 ]3 L- E9 {
preresult /= Num;
! M5 M9 \5 Q6 m5 _, Z2 f1 t break;
+ N/ k% c, @7 P }
( N, |: |6 X! R$ K0 k7 c i++;j++;, h1 r3 w- h9 d+ k7 b
}
8 Y' M, H* ?" i# H" r% n" ? return preresult; //进行修正
; o6 j' L8 {6 } p. e6 E" J8 b }( u, N* N" W% f! U6 X/ |
// 打印算式$ j6 C/ R N2 k m% ^4 R! t2 d" J
void ShowFormula(int *Num,int *Sym,int count,int sum)3 A( P8 t$ K" L
{
2 o1 I- ~+ I8 F$ p6 i( Q* k. O- p* ~( S
int i,j,len;" m# w& o& C* ^$ t# Y# i, |3 V" |
char *Formula = (char*)calloc(count*4,sizeof(char));
4 X7 G; f/ g8 p5 p! P4 [3 w7 q char temp[10];
8 C+ l& a* J: S! h `7 G- w- I itoa(Num[0],Formula,10);& \! e% j* j7 q; ?! V
i=1;j=0;
: h' s6 W( m ` while(i6 Y9 K1 g4 o5 w0 ~" P7 [7 s1 J) O
{
' v# P9 I3 ]) S8 K' z$ d3 a# j- Q2 m* F itoa(Num,temp,10);
, B( o& L% g1 `4 C) w len = strlen(Formula);
3 n% C& S: y. h6 }& y7 J' I switch(Sym[j])
( g* V* o( L, w! E) b, d" a" Y9 o {1 e( q2 a" X4 e) C. U( Y5 A+ d
case 1:' W7 J5 W" J. U0 F. i; X; D
case 2:
/ a1 l' R+ t* C1 ]& D/ V- @, M) N' i Formula[len] = cSym[Sym[j]];) X1 J8 s1 T' h- A; o+ n5 y/ Q
strcat(Formula,temp);
! i) X( m' X4 } break;
) d! b" c% L4 o1 [/ x8 B case 3:' Y7 ^- k3 S+ [6 m; w
case 4:. Y) G! i5 t2 x' v, X+ s, K" x' Z
( {: H' P; b: C1 }* M6 r+ u, L // 如果上一个操作符号优先级低于当前的，应加上括号9 |# l) @& K8 v; j6 D
if(j==0 || Sym[j-1] > 2)0 c$ r4 a/ Q, l2 i3 H4 M% l
{
: y; m3 v* I3 Z Formula[len] = cSym[Sym[j]];9 c! |2 m2 g. w' e
strcat(Formula,temp);/ ]2 |& F- L' U5 @+ r) r- q- F* O
}4 Y7 |7 J p- O. t% k
else5 [+ S7 |5 s; ^+ Q
{: S- c; y/ K [0 A* v3 _
int n;
/ d$ k2 c+ ?$ Z. A char *FormulaTemp = (char*)calloc(len+1,sizeof(char));
4 X3 M* C, H8 V T. F* H9 b5 s5 P for(n=0;n: z9 Z# y% G6 K0 u9 @: Z" m
{
2 \7 N. A% \6 p FormulaTemp[n] = Formula[n];
5 Q3 ]/ i; e7 h Formula[n] = 0;$ e) Q* s# r% [6 W* ~' l' e
}
2 ]5 W# b2 P+ Y$ Q, G Formula[0] = '(';
# G+ B2 ?' X+ W7 N' u; i0 }+ Z strcat(Formula,FormulaTemp);
! y& U3 F; J& K5 B) i0 M: N free(FormulaTemp);: P5 m6 L, T0 @9 ]
Formula[len+1] =')';& |" D/ A4 u* q7 g$ ]
Formula[len+2] = cSym[Sym[j]];
' |0 \3 C3 R1 ^) @7 r" y5 r strcat(Formula,temp);
9 k) X& b7 Z% I+ f }. S9 M: p8 f1 z6 @
break;
9 Z8 A6 Z3 ]. {1 M( M: o( f+ B }! v# P2 \0 C/ O% d# u
i++;j++;
* z* h0 |2 I( b! x5 F/ f [ }
- ^+ ^( _ L& W+ B) y' J/ t9 G printf("%s",Formula);* M* D& v1 w$ h) n& v$ i
printf("=%d\n",sum);" N' \) W$ o/ H$ `* s9 B1 C- H' U
free(Formula);
+ `- S2 E& w# ] C9 h+ U5 S; z }# a' m" Y* n; {6 p! U
# [! g8 J9 \+ l: x" j9 V) p" |8 Y
// 以当前数组为基础得到一个从小到大排列的数组
1 P$ K; {5 [/ F( a b/ T2 z // 返回非0表示穷举结束7 L! x- t2 {/ I. {. c1 A; c
int EnumArray(int *Num,int min,int max,int count). x* i2 j$ R$ A$ F- r" _ d
{. F8 N% X: T ~- `* a2 Y u' N
int i,top;4 q- x/ l! L! ~0 b: m
top = count-1;) v: ^: [% v' y( p: z: P2 v* e& c
Num[top]++; h2 E# A. ?8 q& [6 ]0 @
while(Num[top]>max-count+top+1 && top>=0) {4 E3 O0 u( I! q9 v: @6 `& ~
{# j& g$ |* |, F- {
top--;
2 l9 N( H" O# O/ f/ i. C3 G Num[top]++;5 w6 B% W; ]8 M% y
}
1 W e( r. C1 q0 \ for(i=top+1;i- O# i7 k& h% e2 E/ l
{& X* ~, w8 B& W0 M# f- ?! _
Num = Num[i-1]+1;' ?1 a0 a, X: Z7 }
}& l4 U, O. i+ w9 B; I5 y- Y3 L {" ?
if(Num[count-1] > max) return 1;
0 V {; e( }8 ]; c else return 0;
. P& B2 |, {5 V6 S6 n. A0 r5 { }
! }, U1 h2 Y8 T, U ^, ~
% K6 F" x' U. O" A- q // 不允许重复的初始化数组* I0 s5 V9 c4 R8 T
void InitArray(int *Num,int min,int max,int count)
# L9 r, g9 ]- ~" p+ \ {/ ~& @) |# m5 o8 i$ r# U; ]
int i;
+ ?0 I: m" i; `- ~8 q for(i=0;i=min+i;
' K1 o+ G* V; X Num[count-1]--;
9 {, O% `: k- k/ Z0 ^/ ?! W }
" T3 U( q) c' S! [% P' K5 y8 Q6 [, f
4 M* u( u; R/ i+ r: z9 `2 q
, A7 @! X* Z# _' H5 Y! \; R4 C/ s8 W
* O9 S h& `7 G' ]$ z- K [此贴子已经被作者于2004-5-2 14:50:47编辑过] |
|
IP卡
狗仔卡
发表于 2004-4-27 17:53:00
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
分享
顶
踩
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
千斤顶
显身卡
发表于 2004-5-1 09:53:00
楼主
/1 
