巧填奇数阶幻方(魔方阵)[转]
一、什么叫幻方?
(通俗点说)把一些有规律的数填在纵横格数都相等的正方形图内,使每一行、每一列和每一条对角线上各个数之和都相等。这样的方阵图叫做幻方。
幻方又分为奇数阶幻方和偶数阶幻方。奇数阶幻方是指横行、竖列都是单数(即3、5、7、9……)的方阵图。偶数阶幻方是指横行、竖列都是双数(即4、6、8、10……)的方阵图。
二、奇数阶幻方的填法。
奇数阶幻方中最简便的一种就是三阶幻方,又称“九宫图”。
平常我们遇到这类题都是用分析、分组、尝试的方法推出,这种方法较麻烦,如果是五阶幻方、七阶幻方就更困难了。
有一种方法不仅能很快地填出三阶幻方,还能很快地填出五阶幻方、七阶幻方、九阶幻方……那就是“口诀法”
口 诀
“1”坐边中间,斜着把数填;
出边填对面,遇数往下旋;
出角仅一次,转回下格间。
注意:
(1)这里的“1”,是指要填的这一列数中的第一个数。
(2)“1”坐边中间,指第一个数要填在任何一边的正中间的空格里。
(3)从1到2时,必须先向边外斜(比如:第一个数填在上边的正中间,填第二个数时,要向左上方或右上方斜),填后面的数时也要按照同样的方向斜。
一) 大数阶乘
/*时间限制:3000 ms | 内存限制:65535 KB 难度:3 描述 我们都知道如何计算一个数的阶乘,可是,如果这个数很大呢,我们该如何去计算它并输出它? 输入 输入一个整数m(0<m<=5000) 输出 输出m的阶乘,并在输出结束之后输入一个换行符 样例输入 50 样例输出 30414093201713378043612608166064768844377641568960512000000000000 */ #include<stdio.h> #define MAXLEN 100000 int Factorial(int n,int a[]){ int sum,i,j,temp; sum=0;//最高位下标; a[0]=1; for(i=1;i<MAXLEN;i++){ a[i]=0; } for(i=2;i<=n;i++){ for(j=0;j<=sum;j++){ a[j]*=i; } for(j=0;j<sum;j++){ temp=a[j]; a[j]=temp%10;//本位数值; a[j+1]+=temp/10;//进位; } while(a[sum]>9){ temp=a[sum]; a[sum]=temp%10; sum++; a[sum]=temp/10; } } //printf("%d/n",a[sum]); return sum; } int main(){ int n,a[MAXLEN],sum,i; while(scanf("%d",&n)!=EOF){ if(n<=0||n>5000){ break; } sum=Factorial(n,a); for(i=sum;i>=0;i--){ printf("%d",a[i]); } printf("/n"); } }
unsigned int factory(int *a, const int n) { int i,j,temp; //最高位 int sum = 0; //初始化的值 a[0] = 1; for(i = 0; i < MAXLEN; ++ i) { a[i] = 0; } //开始计算 for(i = 2; i <= n; ++ i) { //每一位相乘 for(j = 0; j <= sum; ++ j) { a[j] *= i; } //对除最高位的每一位进行进位检测 for(j = 0; j < sum; ++ j) { temp = a[j]; a[j] = temp % 10; a[j + 1] += temp / 10; } //最高位进位 while(a[sum] > 9) { temp = a[sum]; a[sum] = temp % 10; a[++sum] = temp / 10; } } return sum; }
二)环形旋转输出
/*在现实生活中,我们时常碰见这样形式的数据遍历或者输出数据。
1 2 3
8 9 4
7 6 5
像这样的形式,我们可以锁定一定的算法,准确地打印数据。下面是一种实现方法:
*/
#include "stdio.h"
int main(int argc, char* argv[])
{
int i,j,m,n,k=0;
printf("Input the number of n:");
scanf("%d",&n);
int **a=new int*[n];
for(i = 0;i < n;++ i)
{
a[ i ] = new int[ n ];
}
//It uses to control the count of for
if(n % 2 == 0)
{
m = n/2;
}
else
{
m = n/2 + 1;
}
//Traversal
for(i = 0;i < m;i ++)
{
for(j = i;j < n - i;j ++)
{
k ++;
a[i][j] = k;
}
for(j = i + 1;j < n - i;j ++)
{
k ++;
a[j][n - i - 1] = k;
}
for(j = n - i - 2;j >= i;j --)
{
k ++;
a[n - i - 1][j] = k;
}
for(j = n - i - 2;j >= i + 1;j --)
{
k ++;
a[j][i] = k;
}
}
//Print data
for(i = 0;i < n;i ++)
{
for(j = 0;j < n;j ++)
{
printf("%4d",a[i][j]);
}
printf("\n");
}
for(i = 0;i < n;i ++)
{
delete [] a[i];
}
delete a;
return 0;
}
顺时针的打印
/*在现实生活中,我们时常碰见这样形式的数据遍历或者输出数据。 7 8 9 6 1 2 5 4 3 像这样的形式,我们可以锁定一定的算法,准确地打印数据。下面是一种实现方法: */ #include "stdio.h" int main(int argc, char* argv[]) { int i,j,m,n,k; printf("Input the number of n:"); scanf("%d",&n); k = n * n; int **a=new int*[n]; for(i = 0;i < n;++ i) { a[ i ] = new int[ n ]; } //It uses to control the count of for if(n % 2 == 0) { m = n/2; } else { m = n/2 + 1; } //Traversal for(i = 0;i < m;i ++) { for(j = n - i -1; j >= i; j --) { a[i][j] = k; -- k; } for(j = i + 1; j < n - i - 1; j ++ ) { a[j][i] = k; k --; } for(j = i; j < n - i - 1; j ++) { a[n - i - 1][j] = k; k --; } for(j = n - i - 1; j >= i + 1; j --) { a[j][n - i - 1] = k; k --; } } //Print data for(i = 0;i < n;i ++) { for(j = 0;j < n;j ++) { printf("%4d",a[i][j]); } printf("\n"); } for(i = 0;i < n;i ++) { delete [] a[i]; } delete a; return 0; }
三)求数组的每行和每列的和
#include "stdio.h" #include "iostream.h" int main(int argc, char* argv[]) { int i,j,a[5][4] = {{1,2,3},{4,5,6},{7,8,9},{10,11,12}}; printf("cout the array:/n"); for(i=0;i<5;i++) { for(j=0;j<4;j++) { printf("%4d",a[i][j]); } cout<<endl; } cout<<endl; for(i=0;i<4;i++) { for(j=0;j<3;j++) { a[i][3]+=a[i][j]; a[4][j]+=a[i][j]; a[4][3]+=a[i][j]; } } cout<<"the end of the array:"<<endl; cout<<endl; for(i=0;i<5;i++) { for(j=0;j<4;j++) { printf("%4d",a[i][j]); } cout<<endl; } cout<<endl; return 0; }
四)二分法查找算法
#include "stdio.h" #define M 10 /* **二分法查找技术要点: **@1 要对已经有的数据进行有规律的排序 **@2 然后,再进行算法分析 */ int main(int argc, char* argv[]) { static int a[M]={-12,0,6,16,23,56,80,100,110,130}; int n,low,mid,high,found; low=0; high=M-1; found=0; printf("Input a number to be searched:"); scanf("%d",&n); while(low<=high) { mid=(low+high)/2; if(n==a[mid]) { found=1; break; } else if(n>a[mid]) { low=mid+1; } else { high=mid-1; } } if(found==1) { printf("the index of %d is %d/n",n,mid+1); } else { printf("there is not %d/n",n); } printf("/n"); return 0; }
用递归方法实现:
int RecBinarySearch(int a[],int first,int last,int item) { if(first> last)//当要查找的值不在数组a中,递归调用将会使first> last return 0xFFFFFFFF; int pos=0; pos=(first+last)/2; if(item <a[pos]) RecBinarySearch(a,first,pos-1,item); else if(item> a[pos]) RecBinarySearch(a,pos+1,last,item); else return a[pos]; }
五)给一个奇数阶N幻方,填入数字1,2,3...N*N,使得横竖斜方向上的和都相同
//给一个奇数阶N幻方,填入数字1,2,3...N*N,使得横竖斜方向上的和都相同 #include <iostream.h> #include <iomanip.h> #include <cmath> //using namespace std; int main() { while(1) { int n; cout<<"please input the number of n:"; cin>>n; if(n%2!=0) { int i; int **Matr=new int*[n];//动态分配二维数组 for(i=0;i<n;++i) { Matr[ i ]=new int[n];//动态分配二维数组 } //j=n/2代表首行中间数作为起点,即1所在位置 int j=n/2,num=1;//初始值 i=0; while(num!=n*n+1) { //往右上角延升,若超出则用%转移到左下角 Matr[(i%n+n)%n][(j%n+n)%n]=num; //斜行的长度和n是相等的,超出则转至下一斜行 if(num%n==0) { i++; } else { i--; j++; } num++; } for(i=0;i<n;i++) { for(j=0;j<n;++j) cout<<setw((int)log10(n*n)+4)<<Matr[ i][ j ];//格式控制 cout<<endl<<endl;//格式控制 } for(i=0;i<n;++i) { delete [ ]Matr[ i ]; } } else { cout<<"请输入一个奇正整数!/n"; } } return 1; }
六)杨辉三角递归算法
#include <stdio.h> int f(int n,int m) { if (m == n) /* 三角形外面的一条边 */ { return 1; /* 这边上的元素都是1 */ } else if (m == 1) { return 1; /* 里面的边 */ } else { return f(n - 1,m - 1) + f(n - 1,m); } } int main(int argc, char* argv[]) { int n = 5; /* 行数 */ int i,j; for (i = 1;i <= n;i++) { for (j = 1;j <= i;j++) { printf("%4d",f(i,j)); } printf("/n"); } return 0; }
七)约瑟夫环
/*如题: 用户输入M,N值,从1至N开始顺序循环数数,每数到M输出该数值,直至全部输出。写出C程序。 循环链表,用取余操作做 代码如下: */ #include "stdio.h" int main() { int k,j,i; int nNum,nStart,nDistance; /** ** nNum 总共有的数目 ** ** nStart从哪个数据开始输出 ** ** nDistance 每隔几个数据输出 */ printf("please input nNum,nStart and nDistance:"); scanf("%d%d%d",&nNum,&nStart,&nDistance); int *nKey = new int [nNum]; for(i = 0;i < nNum ;i ++) { nKey[i] = nDistance; } k = 0; for(i = 0;i < nNum;i ++) { j = 1; while(j < nStart) { while(nKey[k] == 0) { k = (k + 1) % nNum; } j ++; k = (k + 1) % nNum; } while(nKey[k] == 0) { k = (k + 1) % nNum; } printf("%4d",k + 1); nStart = nKey[k]; nKey[k] = 0; } printf("\n"); return 0; }
八)桶排序
// 有1,2,....一直到n的无序数组,求排序算法,并且要求时间复杂度为O(n),空间复杂度O(1),使用交换,而且一次只能交换两个数。 #include<iostream.h> int main(){ int a[] = {10,6,9,5,2,8,4,7,1,3}; int len = sizeof(a) / sizeof(int); int temp; for(int i = 0; i < len; ) { temp = a[a[i] - 1]; a[a[i] - 1] = a[i]; a[i] = temp; if ( a[i] == i + 1) i++; } for (int j = 0; j < len; j++) cout<<a[j]<<","; return 0; }
九)母牛生小牛问题
/*一个牧场,买了一头一岁大的母牛,母牛3岁后,每年都能生一只母牛,现在编一段程序,计算该牧场20年后有多少头母牛 解析: 每年的牛数 = 前一年的牛数 + 这年新出生的牛数 这年新出生的牛数 = 三年前的牛数 //因为牛要三岁后才能生育 所以:每年的牛数 = 前一年的牛数 + 三年前的牛数 即 f(n) = f(n-1) + f(n-3) */ #include <stdio.h> int f(int nY) { if (nY == 1) { return 1; } else if (nY == 2) { return 1; } else if (nY == 3) { return 2; } return f(nY -3) + f(nY-1); } void main() { printf("%d\n", f(20)); }
十)寻找马鞍点
#include "stdio.h" #define M 3 #define N 4 void minmax(int b[M][N]) { int i,j,k=0; int min[M],max[N]; for(i=0;i<M;i++) { for(j=0;j<N;j++) { printf("%3d",b[i][j]); } printf("/n"); } for(i=0;i<M;i++)//计算找出每行的最小元素,放入min[M]中 { min[i]=b[i][0]; for(j=0;j<N;j++) { if(min[i]>b[i][j]) { min[i]=b[i][j]; } } } for(i=0;i<N;i++)//计算找出每列的最大元素,放入max[N]中 { max[i]=b[0][i]; for(j=0;j<M;j++) { if(max[i]<b[j][i]) { max[i]=b[j][i]; } } } for(i=0;i<M;i++)//按照题目意思,进行匹配 { for(j=0;j<N;j++) { if(min[i]==max[j]) { printf("马鞍点是:(%d,%d):%d/n",i+1,j+1,b[i][j]); k=1; } } } if(k==0) { printf("没有马鞍点!/n"); } } int main(int argc, char* argv[]) { int a[M][N]; int i,j; printf("请输入%d个数值:",M*N); for(i=0;i<M;i++) { for(j=0;j<N;j++) { scanf("%d",&a[i][j]); } } minmax(a);//调用minmax()函数找马鞍点 return 0; }
C语言实现 出现次数最多的数字
int _tmain(int argc, _TCHAR* argv[]) { int list[]={1,2,3,4,4,3,2,1,1,2}; int length =sizeof(list)/sizeof(int); printf("测试数组为:"); for(int i =0;i<length;i++) { printf("%d,",list[i]); } int *result; result = new int[length]; int count = 0; // 这个是剩余可用的总数 int has = length; int element; int MaxNum =0; int tempCount; // 循环,直到列表里不再有数据 while (has > 0) { // 拿到最后一个数据 element = list[has - 1]; // 计数 tempCount = 0; // 向前查找相同的 for (int j = has - 1; j >= 0; j--) { // 如果找到,则计数加1,然后将数据和末尾交换 // 这也是为何要从末尾开始循环的理由 if (element == list[j]) { tempCount++; // 将当前位置交换为末尾的数据 // 注意末尾数据是动态变化的 list[j] = list[has - 1]; has--; } } printf("\n修改数组为:"); for(int i =0;i<length;i++) { printf("%d,",list[i]); } // 如果这个计数最大,则更新输出的数据 if (tempCount > count) { count = tempCount; MaxNum =0; result[MaxNum]=element; //printf("%d,",count); // outValue.clear(); // outValue.add(element); } else if (tempCount == count) { // 否则加入到最大数的列表里 // outValue.add(element); MaxNum ++; result[MaxNum]=element; //printf("%d,",count); } } printf("\n出现频率最高的次数是:%d 次", count ); printf("\n出现频率最高次数的数字是:\n"); for(int m =0;m<=MaxNum;m++) { printf("%d,",result[m]); } getchar(); return 0; }
待续。。。