|
问题：求算法及程序由1*1的正方形拼成的长宽分别为m*n的长方形,求长方形对角线穿过小正方形的个数.
答案：↓↓↓ 李唯为的回答： 网友采纳 算法主要是推出函数f[m][n]=m+n-great_common_div(m,n) #include #include #defineabss(x)((x)>(0)?(x):(-x)) #definemins(a,b)((a)>(b)?(b):(a)) usingnamespacestd; intgre_com_div(inta,intb) { if(a==0)returnb; if(b==0)returna; if(!(a&1)&&!(b&1))returngre_com_div(a>>1,b>>1)1,b); elseif(!(b&1))returngre_com_div(a,b>>1); elsereturngre_com_div(abss(a-b),mins(a,b)); } intmain() { intm,n; while(scanf("%d%d",&m,&n),m,n)//inputm,nandm,n!=0 { printf("Cross%dsquare(s)n",m+n-gre_com_div(m,n)); } return0; } | 
