自己写的几个常见的试题的算法

e`/i-x8m-i3z~9J0看了一下传说中的的几道算法题,应该说很常见了,让自己回忆一下,别把大学的东西都丢了.

5] gqMC B9Ja0题目1 ：一个for循环打印出如下图案51Testing软件测试网 UP2^n,|$Np
*51Testing软件测试网%` q2aI8o
***51Testing软件测试网\Lb1U1du'}[
*****
B%T1_$v^'QX0*******51Testing软件测试网o
g;Vb*X.vM
*****
6w}Hc-S&n9n0***51Testing软件测试网&{6p_R:a6R5|1r
*51Testing软件测试网-}4R5A!GE Xi4^,K+@

R"t-^8Lj Or'V Q,Z0下面是自己写的比较通用的算法,LINE_是从上到最长行的行数.JUMP是每行相差的*数.可以随便修改LINE_和JUMP.

"[S7|/Y1I0#include "stdafx.h"
LK(i#S4W hk _
F/U F0#define LINE_ 6   //行数51Testing软件测试网:e(VW8C `B/D+h
#define JUMP 2    //等差

x+~B"|%BEK0int main(int argc, char* argv[])51Testing软件测试网4P/]0i:k:R}5Oh0Hm
{51Testing软件测试网5K,Z ~d,Sa~;L5bB
 int i,tag=1,k=0;51Testing软件测试网&z)r:TX~1lp!Mp^
 int flag = 0;51Testing软件测试网YCj [:j\Y;Qg`
 int LINE = LINE_-1;
K;FrI }0 for(i = 1; i < 100; i++){
-w+}
[8M G#g ?3AH!T0  if(i >= (LINE*JUMP+1)){
&M_ gv+QK4?4C"T0   if(i == (LINE*JUMP+1)){51Testing软件测试网 m8G4CG6@o
    printf("*\n");
!vPO {'C |9A \Hu/@p0    tag = tag - JUMP;
~/g-C*wq-q Xj0   }51Testing软件测试网|iEx9j
   printf("*");
T3B$a2AY[)ER0   k++;51Testing软件测试网|*[#a4P#vAd;F
   if(k == tag){
gF?S,c*i0    printf("\n");51Testing软件测试网2_Qu'E;mLB
    tag = tag - JUMP;
_6Z`\)OG(u`0    k=0;
Np%l$i y,] q2kJ0    if(tag <= 0){51Testing软件测试网Zh@+i2L!}M
     break;51Testing软件测试网S)cf"{;e4YZQ
    }
?y-OTIr?S#i0Y0   }
_:\\kkH*Xw0  }else{51Testing软件测试网yS^-c }!KCK0R%J
   printf("*");51Testing软件测试网6{a6h(A!Yv3j~
   if(i == tag){
2M%gDaO7oZ#wu8d0    printf("\n");
,M_5B6A C wd0    tag = tag + JUMP;51Testing软件测试网 m}/r Q^3j }
    i = 0;
;P'kk2Q9N s0   }51Testing软件测试网-o,ew\|D
  }51Testing软件测试网,zttp9Pi
 }
nB1o#?
y0 return 0;
0x)[e%J5nY;Pq0}

51Testing软件测试网zT6i6}5aM

Dsy)`#dZ0题目2 :  图表中共有1－9，9个数字，横、竖、斜三个方向加起来都是15,就是编写程序输出所有这样的表，上图是三行三列的，还应能算用1－16的四行四列的。

       下面是自己写的算法,LEN是矩阵的阶.CON是从1到CON的数.可以任意修改LEN和CON,也可以修改MAIN函数里的初始化数值,都可以求出来的;

rI1^yUN~ C0       我用的算法比较笨,我直接用全解空间来递归回溯,算3阶的时候很快,因为只要循环9*8*7*6*....*1次,也就是36万2千880次,当然,解比较靠前的时候会少算很多.代码应该有很多判断的地方可以优化.不过在算4阶的时候就头大了,因为全解空间会有16*15*14*...*2*1次,也就是20万亿多次,估计没4到5个小时是算不完的了.自己也在想差1阶差那么多啊,有点棋盘放米那故事的味道.51Testing软件测试网Ah&M7S;l~[]pM

!PY!K)j-R'SD6aO'b0      不过我的算法的确可以通过加入前期判断来优化或者改变CHECK方法和减少解空间入手,现在这个解空间实在太大了.网上评论有个牛人写了个算法半小时跑完5阶的.我有点晕.

#include "stdafx.h"51Testing软件测试网]#tn6{!j3c5pj)`
#define LEN 3
0E[COt2Y"dO2j[3h0#define CON 9

int Array[LEN][LEN];//矩阵51Testing软件测试网t[1r0Xp,x
int Num[CON];//从1到CON的所有整数

int check(int array[LEN][LEN]){51Testing软件测试网ga9? p%L!z*cJ

(K&KugJ(FJ.t%T0//check函数还没有写对斜方向的约束,不过不影响程序运行,出来的结果应该是所有

@5Q*eo6e
Z!U0//横和竖都相等的矩阵.不过解空间大了影响速度,如果加入斜向的约束和重新提取51Testing软件测试网DxJ.NG6A9F ~%I%{ x

S0? j#s{kJ0//递归回溯解空间的话应该会有非常大的提高.51Testing软件测试网7c9{]~mS/cG"Vt

?fK,{@*\+[E.c051Testing软件测试网h!v%e6MI[6h4]y
 int sum=0,row=0,col=0,i,j=0;51Testing软件测试网CBNRX
 for(i=1;i<=CON;i++){
? ZYVz1H2P-l0  sum = sum + i;51Testing软件测试网;}j/{f3S6ka9@
 }
-OW9d%rj2W0 sum = (10*sum/LEN)/10;
T?{+j Fs0 for(i=0;i<LEN;i++)51Testing软件测试网(H2R[#w2e
 {
Yqyp(}~t5e0  row = 0;
9pW/[D]7R X3x0  for(j=0;j<LEN;j++){
7l4jw#BAw0   row = row + array[i][j];51Testing软件测试网-K1En1zpWx:C
  }
.\4J'dcBQY0  if(row!=sum){
BAg`
w7I0   return 1;51Testing软件测试网 Y2]&Z]'cr
  }51Testing软件测试网B9B`$`H)DB\
  if(row>sum){
(S~Khf+q8w0   return 2;
@kF4B%Y3]0  }51Testing软件测试网)o{"GyLQP@n{5w/h
  col = 0;51Testing软件测试网V.Pl"[:E
  for(j=0;j<LEN;j++){
Hp3ikV }*_|0   col = col + array[j][i];51Testing软件测试网t7j'sE Us9q,n
  }51Testing软件测试网H6z
\ Crv*?q:{
  if(col!=sum){
k5V#c'[AIF2e^We0   return 1;51Testing软件测试网 R)I+bpd)t
  }
w6D2m.id#eVG8[2aj0  if(col>sum){
/TT)vQxJn0   return 2;51Testing软件测试网}q^*i%M6B R X
  }51Testing软件测试网g9{6wZQ
 }51Testing软件测试网V"\is+D3f[q7zp
 return 0;51Testing软件测试网Y8qMR2[nk
}51Testing软件测试网3f;X@2B0?6z*FY#B

int EQ(int array[LEN][LEN],int seat){51Testing软件测试网 lM.g.v u m#Y,fI
 int i,j,d,tmp=0;
$`yJ1?oK&Dw$u0 int row,col;51Testing软件测试网%SF\m3{La
K
 int result;51Testing软件测试网h+NwK+N-oQW(UG
 row = seat%LEN;51Testing软件测试网(fG'gK z;@s,BCj
 col = seat/LEN;51Testing软件测试网5vY6R7tL,GN6w ?
 51Testing软件测试网#\-uZ&S'U]K.O
 for(i=0;i<CON;i++)51Testing软件测试网+Z;}"d"E0kRAt
 {
V|H9c;CXt*Y0  if(Num[i]==0||Num[i]==tmp){51Testing软件测试网 o{8pHZL*]cr
   continue;51Testing软件测试网$@De2H~q(p
  }else{
9_Gwf$s#_8t'm4D0   array[row][col] = Num[i];
X[7[7A;f)N0   tmp = Num[i];51Testing软件测试网8`,XZ LR
   Num[i] = 0;51Testing软件测试网%^c$L;F9HB5hA
  }
-{p`6L sPT"\\0  result = check(array);
'G+wWQ;W%k0  if(result==0){
#SL
H f9qs^6M0   printf("\nseat: \n");51Testing软件测试网%}KF,_p x ok{:XA
   for(j=0;j<LEN;j++){51Testing软件测试网&J5W.]P pEhm I
    for(d=0;d<LEN;d++){
9c4D!Q!t'zq:i/o0     printf(" %d  ",array[j][d]); 51Testing软件测试网Pj:ae!m
    }
8PDb1p1R1k0    printf("\n");51Testing软件测试网S*K1aJD
   }51Testing软件测试网R!~am_#iM,rR+k ivP
   return 0;51Testing软件测试网4Bow1REU?gA |
  }51Testing软件测试网F8GcF%d
  if(result==2){51Testing软件测试网2pq0E9c
~f8B1b
   array[row][col] = 0;
L?z9i.s8u0   Num[i] = tmp;51Testing软件测试网pE)~,H-fo
   continue;
S1e1px4p Ho0  }51Testing软件测试网4n!R:_R b8j'is(T
  EQ(array,seat+1);51Testing软件测试网4]_fFz
  array[row][col] = 0;
0E}&L3A5F#YWqW"Pk0  Num[i] = tmp;
a5L'r4g ``z$i0 }51Testing软件测试网-W7ES G_&a
 return 1;51Testing软件测试网"p9|p.gV0L(QA
}51Testing软件测试网
a&}(K n
Z7l8eI,P
C

int main(int argc, char* argv[])
3D0M Lp}Bk0{51Testing软件测试网`1y7uk9u9?&L
 int m,n,num;51Testing软件测试网~E h5W
W7Lk4h
 for(num=0;num<CON;num++){
r,IVt(O)V0  Num[num]=num + 1;
7A2] S:^!E0 }
6^DLf1iQW#r0 for(m=0;m<LEN;m++){
:F E0dPp0  for(n=0;n<LEN;n++){
#?+nM
k7})gN{vS;G0   Array[m][n]=0;
Bc,X?&R]u(C0  }51Testing软件测试网D9Wj)l"P!c)@#}
 }
~PxMT"JA+F0 EQ(Array,0);
/y'bR*MN0 return 0;
prCds i0}