生成各種矩陣是競賽時經(jīng)常考的一種題目,如何用C語言或C++生成以下形式幾種矩陣:

第一種矩陣:

1 2 9 10
4 3 8 11
5 6 7 12
16 15 14 13


第二種矩陣蛇形)

1 2 6 7
3 5 8 13
4 9 12 14
10 11 15 16


第三種矩陣:

1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7


第四種矩陣:

7 6 5 16
8 1 4 15
9 2 3 14
10 11 12 13


規(guī)律提示：

1.1->2 9->10
4<-3 8 11
5->6->7 12
16<-15<-14<-13
2.每個左上三角的數(shù)都是連續(xù)的
3.一個回旋陣，從外到里是連續(xù)的。
4.同樣是回旋，從里到外是連續(xù)的。



第一種矩陣算法：

#include<iostream.h>
#include<iomanip.h>

void main()
{
const int N=20;
int i=0,j=0,a[N][N];
int lap=1,m=1,n;
while(1)
{
cout<<"\ninput matrix row N(N>=2): ";
cin>>n;
cout<<endl;
if(n>=2) break;
}
a[j]=m++;
lap++;
while(lap<=n)
{
if(lap%2==0)
{
for(j++;i<lap;i++)
a[j]=m++;i--;
for(j--;j>=0;j--)
a[j]=m++;j++;
}
else
{
for(i++;j<lap;j++)
a[j]=m++;j--;
for(i--;i>=0;i--)
a[j]=m++;i++;
}
lap++;
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cout<<setw(4)<<setiosflags(ios::left)<<a[j];
cout<<endl;
}
cout<<endl;
}


第二種矩陣算法：(蛇形)

#include<iostream.h>
#include<iomanip.h>

void main()
{
const int MAXLEN=10;
int nLen;
int nSnake[MAXLEN][MAXLEN];
do
{
cout<<"\ninput an integer less then "<<MAXLEN<<": ";
cin>>nLen;
cout<<endl;
}while(nLen>MAXLEN);
int i=0,j=0,s=1,nNum=1;
//s標記升降方向，斜向上為升(s==1)，斜向下為降(s==-1)
while(1)
{
if(s==1)
{
nSnake[j]=nNum;
if(i-1<0)
{
if(j+1==nLen)
i++;
else
j++;
s=-1;
}
else
if(j+1==nLen)
{
i++;
s=-1;
}
else
{
i--;
j++;
}
}
else
{
nSnake[j]=nNum;
if(j-1<0)
{
if(i+1==nLen)
j++;
else
i++;
s=1;
}
else
if(i+1==nLen)
{
j++;
s=1;
}
else
{
i++;
j--;
}
}
nNum++;
if(nNum>nLen*nLen)
break;
}
for(i=0;i<nLen;i++)
{
for(j=0;j<nLen;j++)
cout<<setw(4)<<setiosflags(ios::left)<<nSnake[j];
cout<<endl;
}
cout<<endl;
}


第三種矩陣算法：

#include<iostream.h>
#include<iomanip.h>

void main()
{
const int N=20;
int i=0,j=0,a[N][N],n;
int m=1,x1,x2,y1,y2,s=1;
//x1,x2,y1,y2為上、下、左、右邊界
//s標記數(shù)組元素升降，s==1為升，s==-1為降
while(1)
{
cout<<"\ninput matrix row N(N>=2): ";
cin>>n;
cout<<endl;
if(n>=2)
break;
}
x1=0;y1=0;x2=n;y2=n;
while(1)
{
if(s==1)
{
for(j;j<y2;j++)
a[j]=m++;
j--;i++;y2--;
for(i;i<x2;i++)
a[j]=m++;
i--;j--;x2--;
s=-1;
}
else
{
for(j;j>=y1;j--)
a[j]=m++;
j++;i--;y1++;
for(i;i>=x1+1;i--)
a[j]=m++;
i++;j++;x1++;
s=1;
}
if(m>n*n)
break;
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cout<<setw(4)<<setiosflags(ios::left)<<a[j];
cout<<endl;
}
cout<<endl;
}


第四種矩陣算法：

#include<iostream.h>
#include<iomanip.h>

void main()
{
const int N=20;
int i=0,j=0,a[N][N],n;
int m,x1,x2,y1,y2,s;
//x1,x2,y1,y2為上、下、左、右邊界
//s標記數(shù)組元素升降，s==1為升，s==-1為降
while(1)
{
cout<<"\ninput matrix row N(N>=2): ";
cin>>n;
cout<<endl;
if(n>=2)
break;
}
m=n*n;
x1=0;y1=0;x2=n;y2=n;
if(n%2==0)
{j=n-1;y2=n-1;s=1;}
else
{i=n-1;y1=1;s=-1;}
while(1)
{
if(s==1)
{
for(i;i<x2;i++)
a[j]=m--;
i--;j--;x2--;
for(j;j>=y1;j--)
a[j]=m--;
j++;i--;y1++;
s=-1;
}
else
{
for(i;i>=x1;i--)
a[j]=m--;
i++;j++;x1++;
for(j;j<y2;j++)
a[j]=m--;
j--;i++;y2--;
s=1;
}
if(m<1)
break;
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cout<<setw(4)<<setiosflags(ios::left)<<a[j];
cout<<endl;
}
cout<<endl;
}
八皇后問題


通過創(chuàng)建一個8元素數(shù)組queenlist，遞歸函數(shù)placeQueen（）具體執(zhí)行此回溯算法。此數(shù)組的每個索引值都對應著棋盤上的一列，queenlist[col]值就是皇后所處的安全行數(shù)row。下面程序聲明一個棋盤board，再使用setQueens（）函數(shù)確定皇后再棋盤上8個安全位置。最后調用drawBoard（）函數(shù)再棋盤上顯示答案。
//文件：prg15——6.cpp
//此程序可以解決八皇后問題。程序提示用戶輸入皇后在0列的起始行并調用遞歸函數(shù)
//queens（）確定是否有解決方案。如果有則將皇后的位置傳到chessboard對象board
//并調用其drawBoard（）函數(shù)顯示皇后的布置。
#include<iostream.h>
#include”d_queens.h”
using namespace std；
int main()
{
int row；
vector<int>queenlist(8)；
chessboard board；
//為0列皇后輸入起始行
cout<<”Enter row for queen in column 0：”;
cin>>row；
cout<<endl；
//查看是否有解決方案
if (queens(queenlist, row))
{
board.setQueens(queenlist)；
//顯示解決方案
board.drawBoard()；
}
else
cout<<”No solution”<<endl；
return 0；
}
第一次運行結果

0 1 2 3 4 5 6 7

0 Q

1 Q

2Q

3 Q

4 Q

5 Q

6 Q

7 Q



第二次運行結果

0 1 2 3 4 5 6 7

0 Q

1 Q

2 Q

3

4 Q

5Q Q

6 Q

7 Q費爾馬“二平方”素數(shù)


除了2這個特別的素數(shù)外，所有的素數(shù)都可以分成兩類：第一類是被4除余1的素數(shù)，如5，13，17，29，37，41；第二類是被4除余3的素數(shù)，如3，7，11，19，23，31。第一類素數(shù)都能表示成兩個整數(shù)的平方和(第二類不能)，例如：5=1*1+2*2、13=2*2+3*3、17=1*1+4*4、29=2*2+5*5...這就是著名的費爾馬“二平方”定理。有趣的是：上述等式右側的數(shù)有的又恰恰是兩個素數(shù)的平方，如13、29，我們就把這樣的素數(shù)叫作費爾馬“二平方”素數(shù)，即是如果一個素數(shù)能夠表示成兩個素數(shù)的平方和的形式，例如：F=X*X+Y*Y (1)，其中F、X、Y都是素數(shù)，它就是費爾馬“二平方”素數(shù)。

編程思路：

本文擬用C++編程，求42億之內(本人只算了10萬以內的)的費爾馬“二平方”素數(shù)。如果按定義從左向右，先求一個素數(shù)F，然后再去找相應的素數(shù)X、Y，工作量重復太大。我們可以對上述公式進行分析：
1、左側素數(shù)F肯定是奇數(shù)，那么右側兩個素數(shù)的和也應該是奇數(shù)，所以X和Y為一奇一偶(奇數(shù)的平方還是奇數(shù)，偶數(shù)的平方還是偶數(shù))。X、Y要求是素數(shù)，而既是偶數(shù)又是素數(shù)的數(shù)只有一個——2，這樣我們就可以確定其中一個為2(這里設X=2)。所以(1)式可以簡化為：F=2*2+Y*Y (2)，費爾馬“二平方”素數(shù)的表示形式是惟一的。
2、按(2)式由大到小找素數(shù)Y，計算出加上4(2*2)后是否等于F，判斷其是否素數(shù)。
3、求出素數(shù)Y后將其保存起來，在判斷其它數(shù)是否素數(shù)時可直接用已求出的素數(shù)去除，如此反復。

算法源代碼如下：

#include<iostream.h>
#include<iomanip.h>

unsigned int a[10000],n=0,c=0;
//prime array,match counter,array counter

void ScreenOut(unsigned long int prime)
{
unsigned int p;
for(p=c-1;p>0;p--) //from the front one
if(prime==(a[p]*a[p]+4))
{
//cout<<'\n';
cout<<setw(5)<<prime<<" = 2*2 + "<<setw(3)
<<a[p]<<" * "<<setw(3)<<a[p]<<endl;
n++;
}
}

void main()
{
unsigned long int i,count,quantity=100000;
int judgement; //if the number is prime,assign 1
a[0]=2;
for(count=3;count<quantity;count+=2)
{//because odd,jump 2 steps once
judgement=1; //assign 1 every cycle
for(i=3;i<count/2;i++)
{
if(count%i==0)
{
judgement=0;
break;
}
}
if(judgement)
{
a[++c]=count; //if prime,assign to array
ScreenOut(count);
}
}
cout<<"\ntotal of match: "<<n<<'\n'<<endl;
}


結論：

運行程序會發(fā)現(xiàn)，除“29=2*2+5*5”以外，算出來的所有的費爾馬“二平方”素數(shù)個位數(shù)字都是3，相應Y的個位數(shù)字都是3或7。費爾馬“二平方”素數(shù)分布(修改程序中變量x的值得到)也很耐人尋味...(部分省略)

費爾馬“二平方”素數(shù)太少了，40億內才718個(本人的電腦CPU慢，只算了10萬以內的，符合條件的也就只有20個)，千萬分之二還不到呢。隨著數(shù)的范圍的增大，似乎越來越稀少，但再往后永遠是這樣嗎？會不會在某個范圍內反而又稠密起來呢？費爾馬“二平方”素數(shù)是無窮多個呢，還是有限多個呢？如果是有限個，又是多少個呢？最大的一個又是什么數(shù)呢？這些問題的證明可能很簡單，也許很復雜，真說不定會成為像“哥德巴赫猜想”那樣的謎呢！
無厘頭字母題


輸入一系列單字，直到文件尾，將每個字轉換為Pig-latin語，如果單字以輔音字母開頭，則將其第一個字符移到最后一個位置并在結尾增加"ay"。如果單字是以元音字母開頭的，則直接在尾部加上"ay"。列如：
輸入：this is simple
輸出：histay isay implesay


# include <iostream>
# include <cstdlib>
# include <cstring>
using namespace std;

void changeWord(char* a, char* b);
int yWordcmp(char a);
int main()
{
const int SIZE = 50;
char iWord[SIZE];
char oWord[SIZE];
for (int i = 0; i<SIZE; i++)
{
iWord[0]=NULL;
oWord[0]=NULL;
}
cout<<"輸入要轉化 Pig-latin 語:\n";
cin.getline(iWord,SIZE);
changeWord(iWord,oWord);
cout<<"\n轉換結果:\n"<<oWord<<endl;
system("pause");
return 0;
}

void changeWord(char* a, char* b)
{
char c = NULL;
while (*a != NULL)
{
while (! isalpha(*a))
*b++ = *a++;

c = yWordcmp(*a)? NULL : *a++;

while (isalpha(*a))
*b++ = *a++;
if(c) *b++ = c;
*b++ = 'a';
*b++ = 'y';
}
}

int yWordcmp(char a)
{
char yWord[5] = {'a','e','u','i','o'};
for (int i =0; i<5; i++)
{
if ((a == yWord)||(a == yWord-32))
return 1;
}
return 0;
} 年歷的問題


歷法系統(tǒng)我們一直都在使用，它在國際商務和交流中有著廣泛的應用，它是羅馬教皇格利高里的歷法系統(tǒng)。羅馬教皇, 主教, 蒲柏頒布的在基督教領域里使用的歷法。它存在兩個問題，第一個是這個世界絕大多數(shù)不是基督教。第二，基督教歷法事實上是基于早期的歷法系統(tǒng)（朱利安羅馬皇帝的系統(tǒng)），它本身是從古代以及其他的一些歷法演變過來的。為了把它推廣到世界其他國家和宗教，它包含了很多有趣的東西來吸引人們。這學期我們來看一下法國的歷法革命。
法國歷法革命（共和歷法）是在1793年11月24提出的。原因是為什么一部分人（包括法國人）直到1806年1月還沒有聽說這套歷法系統(tǒng)已將廢止了。而且在1871年又從新出現(xiàn)了，但是又一次的不顯著死亡。法國歷法革命有趣的地方是他極力的使用十進制。

共和國的歷法八一年365天或366天分成12個月，每個月30天，再加上另外的5或6天。這些月份是
1,Vendemiaire
2,Brumaire
3,Frimaire
4,Nivose
5,Pluviose
6,Ventose
7,Germinal
8,Floreal
9,Prairial
10,Messido
11,Thermidor
12,Fructidor

這套系統(tǒng)不是把一周分為7天，它把一個月分成3個10天，其中10天的最后一天休息。盡管10天的制度很簡單，但是9天工作一天休息的制度不是很流行，然而羅馬教皇 Gregory 的工作6天休息一天似乎更流行。
這10天分別叫做：Primidi,Duodi,Tridi,Quartidi,Quintidi,Sextidi,Septidi,Octidi,Nonidi,Decadi.

額外的5或6天（365or366-12*30）接著果月(法國共和歷的12月,相當于公歷8月18 日到9月16日)的最后一天叫
1,Jour de la vertu (Virtue Day)
2,Jour du genie(Genius Day)
3,Jour du travail(Labour Day)
4,Jour de I’opinion(Reason Day)
5,Jour des recompenses(Rewards Day)
6,Jour de la revolution(Revolution Day)(the leap day)

法國共和歷是從1792年9月22實施的。這一天變成了1 Vendemiaire共和歷的第一年，（事實上這套歷法直到1973年11月24才被介紹）。閏年的新年那一天被定在秋分（出現(xiàn)在9月22在北半球）為了精確，閏年與羅馬教皇 Gregory 的歷法系統(tǒng)一樣每4年一次閏年（百年除了能被400整除的）。
計算閏年開始于法國共和歷法20年后但是歷法沒有計算。法國共和歷的前20年里，3，7和11時潤年15和20也是 閏年，除了這些以后每4年一次閏年。（包括合適的百年）。

你的任務
作業(yè)目的把羅馬教皇 Gregory 的歷法(即：現(xiàn)在所用的陽歷)換成法國共和歷用C++程序。你可以用任何C++的class，建造或ADT等

有很多方法去完成作業(yè)
1，開始輸入陽歷
2，基于這些數(shù)字，求出自共和歷建立以來的天數(shù)。
3，基于這些數(shù)字，求出自共和歷建立以來的月數(shù)和年數(shù)。
4，最后得出相應的共和歷日期

最初的界面提示如下：
Please enter a Gregorian date (dd mm yyyy):
程序輸出法國共和歷的日期格式：[day][month name][year],例如：6 Nivose 49.因為輸入的是陽歷，有365或366天，而我們要得出的是共和歷，但共和歷只有30*12=360天，所以多出的5，或6天我們就用以上給出的共和歷提供給我們的那幾種名稱來取代（例如：Jour du genie）.如果輸入的陽歷在共和歷之前（即1792年9月22日之前），那么輸出就使用BR(before republic)，意思就是共和歷前多少日期。如果共和歷日期顯示在屏幕上，那么程序宣告終止。

以下是測試程序是否正確，它們是陽歷的新年（1月1日）在共和歷里的日期
year 1: 22 sep 1792
year 5: 22 sep 1796
year 10: 23 sep 1801
year 12 :24 sep 1803
[url]http://bbs.bccn.net/thread-220100-1-1.html[/url]

轉載于:https://blog.51cto.com/qq164587043/105077

總結

以上是生活随笔為你收集整理的经典程序算法问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。