TA的每日心情 | 奋斗
2015-9-17 00:58 |
|---|
签到天数: 1 天 [LV.1]初来乍到
|
以下是引用游侠无极限在2004-5-2 14:41:26的发言：
% a, g8 R! v6 Q+ ?* j3 B#include $ S9 f! A( U- J4 z: d) g. X1 c
#include
/ A) {6 ~5 K* [. ~ \
, ?1 N1 j6 F/ F$ [5 f/ q, d# F. N int EnumFormula(int min,int max,int num,int sum);) F9 ~1 a% {# q5 C
void ShowFormula(int *Num,int *Sym,int count,int sum);
Z8 e/ d, a) N% |5 J! T double GetFormulaVal(int *Num,int *Sym,int count);
+ U2 }. j1 r/ O) H* t: i% l int EnumArray(int *Num,int min,int max,int count);
7 r% u& H, X7 p! X; _/ _& q void InitArray(int *Num,int min,int max,int count);
1 e F. P/ Z( K- w, A const char cSym[5] = {0,'+','-','*','/'};
5 E1 ~. x* P. S# O; ~( f& V7 z' b/ ~: M# c F8 z# ]$ t
int main(int argc, char *argv[])
. l5 c$ k1 Q# J {8 A+ ^ r8 d, G3 s @" d
printf("总计%d个式子\n",EnumFormula(1,10,4,24));
$ L9 U& X( T& V system(" AUSE");
; c0 t" r8 _4 U3 r! V1 ?; J return 0;
( {. @5 e$ H" ~% W }
# E3 Q0 A7 t# x1 w' _6 e0 }& q
, T: _' U1 ~9 y) F. f/ Y* a int EnumFormula(int min,int max,int num,int sum); X0 ^" l$ J6 a1 d2 _; q: L
{/ F6 c; M4 K w% v* ^
int *FormulaNum = (int*)calloc(num,sizeof(int)); //储存操作数
; }7 i- }( @( Q, }0 B4 Q' Z //储存操作符号
7 O$ o7 z6 \4 q4 {8 V( g //最后一位用于穷举结束标记* P' ?/ M( k$ q8 ^% A/ ^
// 1 - 4 代表 '+' '-' '*' '/'/ v9 s0 B' |4 _) F0 g( n& w. w
int *FormulaSym = (int*)calloc(num,sizeof(int));
5 Q2 T' v0 ~$ y
& D% q3 O, a( Q* |+ o0 w- y int result = 0;/ y B5 P2 }/ n7 U
// 初始化操作数和操作符号数组
" \/ h* [ l6 B5 {- c4 J, c) M s! n* Q% E. e3 c- S* h+ q
int i; m6 W3 ]' ]5 c$ U6 V4 Y$ R
/ B- G0 |' J* d for(i=0;i = min;
, s2 e" a4 N1 [$ E+ V2 C) A8 V for(i=0;i = 1;
2 \$ Z( v- ^; g4 K" S! N FormulaNum[0]--;
2 [$ \$ h! J& Q7 U7 ^2 O
( A+ Z: y; J* [ InitArray(FormulaNum,min,max,num);
7 z: V: g7 }! J8 \& ^" b6 B FormulaNum[num-1]++;
* L+ e- [' a V, t // 穷举操作数和操作符号组合1 k% ]1 S8 {0 G- f, S! s
while(FormulaSym[num-1] == 1)
% ]3 C; j9 F" L. s4 B {5 G5 q" d4 s1 [3 X* p' [3 v
double t = GetFormulaVal(FormulaNum,FormulaSym,num) - sum;+ M+ b* C7 h1 u- Y Q" y0 g
if(t>-0.01 && t<0.01)
/ l/ J7 p" k! O( ] {! W4 p: V% J( z& z- P0 V3 i
//printf("%d %d %d %d | %d %d %d ",FormulaNum[0],FormulaNum[1],, j" @2 r% x9 ?! s8 ^+ |- q* }
//FormulaNum[2],FormulaNum[3]," j: {9 \' Y8 o5 D
// FormulaSym[0],FormulaSym[1],$ w; V/ y3 Y8 [+ K
// FormulaSym[2],FormulaSym[3]);
6 @3 r9 u& S) O* I ShowFormula(FormulaNum,FormulaSym,num,sum);
/ D8 u6 z; f6 g5 ]# \ result++;
$ f% u/ u+ U4 g q2 s- O$ w4 c }
' p2 x# U4 m: A. F4 X: Q " E0 Q1 J/ P: q3 q- o, y
// 依次穷举操作数- A( N) N9 J) {
4 A% u, j, d- c" j
//允许数字重复的穷举
9 P B6 ^9 f7 b) R0 E( h //FormulaNum[0]++;2 K" i! u4 Z; \. ~0 Q M1 X
//for(i=0;FormulaNum > max && i
7 |' @% @" ]; a0 A$ g# J/ | //{
- ~' a+ R% [' y- f/ y; E' A // FormulaNum = min;8 s; V7 K! a8 ^8 Z2 ~
// FormulaNum[i+1]++;
' n+ H( ~2 v, h) l( Y //}
6 ^8 P# G5 f7 C7 I // 操作数穷举与操作符号穷举联接
5 ]. X+ L) r; ?" ~( K //if(FormulaNum[num-1] > max)0 ~8 y6 q. E: n: a/ f
//{/ R) w1 c% n2 V0 |. L& V6 J$ l
// FormulaNum[num-1] = min;2 C% _$ O) d( y8 |# X& }* ~
// FormulaSym[0]++;+ X8 D6 t) p4 h
//}2 x" ?6 Y; p* X, j. p/ M
& n: l1 k7 u: x4 K: A+ q% N
// 不允许数字重复的穷举' v$ e+ |5 z* e6 A! [. d* v+ O+ g
// 数字必须从小到大的排列，防止重复; u: U6 o) l5 p5 ~9 J6 Q
if((max - min)< num) exit(0); // 出错$ r' f% t2 y4 t# E# {$ `
0 V. _; j2 ^" Y. k
if(EnumArray(FormulaNum,min,max,num))- m; O9 r# R( a- H# F. T8 B
{
" _8 t) |. z! Q5 M) d FormulaSym[0]++;
/ o( J2 D7 o/ f/ n! W8 F InitArray(FormulaNum,min,max,num);) J; R) q9 J) O' N5 O; C% C
FormulaNum[num-1]++;
2 i0 G# q4 G3 ^1 m }9 j; P- Z Y/ {+ Q
: ?6 ?% X s1 L- s F+ l) z // 操作符号穷举" l9 l- x7 ^/ @
for(i=0;FormulaSym > 4 && i" L- p: t! T- W( } {
5 Q! B9 n8 w0 |# N L FormulaSym = 1;
7 G% p/ t" A4 o, w6 `* T FormulaSym[i+1]++;6 f& }# z: y% ~" {4 [# U# R" |( ?
}3 l" v2 C ^9 R' c' S' A
1 q8 a0 @! U4 Z! U8 L ^' Z" R
} Y& T2 }; O$ m
//释放空间
. V6 ]1 j: x; Y+ y9 J5 ]: o free(FormulaNum);
! W" R& f& Q1 A/ Y free(FormulaSym);" `- U5 p7 t- @1 |+ q- s
return result;
$ t' J$ t: t4 w) U4 F }) V3 ~7 ~! Y0 \
// 计算算式结果7 d/ c h! G( A+ {, `
double GetFormulaVal(int *Num,int *Sym,int count). e7 q, g/ g3 t; r6 D/ M
{" R/ [9 i! Z# X# m
int i,j;
4 _. Q4 [- O9 `' m double preresult;3 B! {- o/ C/ \4 ` T: c Z- w
preresult = Num[0];7 w' U0 `2 `) I* d3 i% i
i=1;j=0;) n8 q% l6 C( v! K# I
while(i- |4 w3 O6 U; \, x* T- \ {; r+ R* t) E6 X9 ^
switch(Sym[j])
$ D; `( ]$ U1 W) U# @ {
, G. F8 J9 g( d% b' G case 1:4 O" e5 G/ p4 q5 ]- N" S/ y8 B+ o
preresult += Num;
& h! v; i* e% ]) O. M break;
3 N" g4 a9 e# j: L8 p8 X case 2:& R* ?7 N. _: C4 {) f, F( Y
preresult -= Num;1 Y7 q& x2 L) F! J+ W/ F# C
break;
2 l) R8 A8 p: U7 T8 W) ^ case 3:! F1 ?# m: I; P$ ~8 ^
preresult *= Num;
2 m/ ~* g1 \0 a9 m6 Y4 D+ E break;+ u9 _% L6 A0 A
case 4:4 v! t" Z" e6 n" l- E0 B( D. O( Y
if(Num == 0) return -1000;5 {/ C9 T) g8 H7 E+ g8 P8 U- G/ e
preresult /= Num; X+ T3 B& t3 F% D/ W D. w5 [& w: I* [
break; I! @$ y$ s% v6 `; s' T3 i
}+ | }# T% g: T+ K& q2 V/ Y
i++;j++;
( i8 t8 F" m4 p$ n$ H }# \* z! ^' f2 Q* j8 n9 V* M9 d' W u
return preresult; //进行修正5 T5 x9 \) i8 X0 K
}
4 @2 ~8 t# n+ f6 J; e // 打印算式
: a) e: P9 j% A. G+ p+ S, c j void ShowFormula(int *Num,int *Sym,int count,int sum)" f8 Q8 _4 @- V6 ~# {3 K& j$ J( N
{, ~2 C% O- ~4 p* O9 y u
( T* Z& L3 n0 a int i,j,len;
0 _) q* }8 b& H! ?/ y" p; A char *Formula = (char*)calloc(count*4,sizeof(char));
5 O% X6 ^2 w! ^2 P9 T) g; W char temp[10];* U$ m/ M. Y( R. [
itoa(Num[0],Formula,10);" H/ C9 F* H J, F0 B7 C0 m- |6 |
i=1;j=0;
( J, R. Z3 B4 C/ X4 d6 ^0 b3 i1 W while(i5 l0 m* R8 q8 f1 o
{
& L% }2 x* P V* i/ n4 H itoa(Num,temp,10);
/ z# F8 _) d/ A1 o, z" O len = strlen(Formula);& U, b* E; i! O9 K
switch(Sym[j])
( u$ X3 L9 t3 X* {' [2 Y {
/ ?4 J8 j2 M6 m) v) q/ i case 1:
: X. z5 r2 w, ~( { case 2:0 M P4 Z% c* s7 v
Formula[len] = cSym[Sym[j]];
4 j4 E$ E' L9 K& s strcat(Formula,temp);
$ c' S* l6 I$ i, H: t7 s3 o break;
, j. p( N5 U, x case 3:
- F! c; | Y8 E7 T2 _ case 4:- k* L/ B; S1 w. C+ |
+ K7 k( v6 C: [1 T/ }; B! Q g7 x // 如果上一个操作符号优先级低于当前的，应加上括号& }+ }, D. q8 U L
if(j==0 || Sym[j-1] > 2)
, b6 e. h, K) z* B5 R {0 P, h4 Q0 g; c# P' g5 I, ]% h6 V
Formula[len] = cSym[Sym[j]];
5 g% n1 d4 L6 @' e! |5 ~- [/ x. X( j strcat(Formula,temp);
- C) G" l- }6 |7 G& [$ N4 s7 | }
6 w3 f) q1 r ^) s1 Q else
* n, w; b8 q# j# U2 x" B {% K; S" t j3 T2 k1 i
int n;
0 p6 z7 X8 m' N% W char *FormulaTemp = (char*)calloc(len+1,sizeof(char));7 n! e- l9 |8 v* O
for(n=0;n1 T' v0 H- |, r! ]2 U' m' A {; r& W ]6 q: I* s( |
FormulaTemp[n] = Formula[n];; X$ F# c' b' ~, w
Formula[n] = 0;
- x' [+ S8 d7 b& V$ d3 [# }) `. n }
" T. v9 P1 O Z Formula[0] = '(';
6 ?; i3 e. T) |/ T strcat(Formula,FormulaTemp);
5 |0 x# m" Q: v) Q- ] free(FormulaTemp);! A. l9 `: x( ^7 p2 U
Formula[len+1] =')';. F3 Y7 F: z' K7 {+ e7 l
Formula[len+2] = cSym[Sym[j]];; t" J2 s" @* F r+ d/ E
strcat(Formula,temp);4 Y, |( Z5 w/ v, j4 h8 X
}+ W1 c m' z5 a4 V, O2 H
break;
2 D( G1 q. U- }2 J }
* o& }- [9 C/ R8 ]7 b% Q! g- Q0 T i++;j++;
W* ?) E6 e5 c2 b: s0 A1 s/ C }
$ p' N3 s& S: k, F. w+ f6 R9 L printf("%s",Formula);" A" a0 J w: ` K6 R
printf("=%d\n",sum);/ |7 J8 T' M# E7 R. g( Y
free(Formula);
9 J3 j, Q. X' O& w- Y- N! O }: D2 I( k- m+ [
" g0 J$ t" b5 i5 n. y4 m" f
// 以当前数组为基础得到一个从小到大排列的数组
! v% o2 j( c2 D0 P$ v; C // 返回非0表示穷举结束- Z1 n) w4 ^$ y- A& P, Y: e
int EnumArray(int *Num,int min,int max,int count)
* Q. E9 c3 F% f5 [/ ?6 A) e. g {( J9 [& B# h: G b$ F w% e
int i,top;
8 P; t' ~% ^0 I$ G. @9 W/ K top = count-1;
: h4 [: ~0 o6 c* `$ A* P Num[top]++;
" [7 R1 e! I* `: l4 u# p3 j3 P5 @ while(Num[top]>max-count+top+1 && top>=0) o \ n9 ^9 I. k. g' D( r
{- c# D, B4 W# j$ z
top--;
* Z- D/ W- a M) R Num[top]++;
+ n: P8 I- j$ V5 d% V) ]/ ~5 b }/ y4 X b& c! V/ ] ~" a t" G
for(i=top+1;i$ ^) X+ w1 M9 |, j% F3 ?( W
{% h; K/ @ c! J! a# b" U
Num = Num[i-1]+1;
g* t+ E! @* m2 t% l3 Z; N3 s: e }
4 r9 d2 E, ~* @, r- k+ u* V: m if(Num[count-1] > max) return 1;
3 a: f3 J: H9 s: d% R% C& Y else return 0;
5 T( o0 F& W3 T2 \+ V. r) @ }1 f! q' t7 p. o9 S$ r9 o2 i+ i
! Y1 v2 O8 |6 t g ~: m, s // 不允许重复的初始化数组
- e& Z6 o- }8 G4 I E; v9 P, v void InitArray(int *Num,int min,int max,int count)
: Z Z+ s" P, ^% N2 }& r {" ~' @; A$ p( G, M) x7 Q% ~" s {4 E
int i;
5 F- @# s: [5 ]0 a# W. w. s for(i=0;i=min+i;3 V& m1 a7 W* k6 \6 B4 {
Num[count-1]--;
0 ?4 r" w4 q$ l I$ a' T }
" j: i2 p5 M& A8 s+ E( M. C0 K' s k. F" A+ C
4 D9 R+ U# E& |* B [0 j. b H3 _ W
1 A' x: h% w, y% T/ b 2 A3 w! y; [. _" ^2 H( e. v
[此贴子已经被作者于2004-5-2 14:50:47编辑过] |
|
IP卡
狗仔卡
发表于 2004-4-27 17:53:00
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
分享
顶
踩
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
千斤顶
显身卡
发表于 2004-5-1 09:53:00
楼主
/1 
