Intro
啊哈，算法封面.png
t1.這篇文章記錄我的一個(gè)學(xué)習(xí)和心得
t2.需要c語言基礎(chǔ)
t3.需要數(shù)據(jù)結(jié)構(gòu)和算法的基礎(chǔ)
t4.Just Do it!
一大波樹數(shù)正在靠近——排序
本節(jié)講的是簡化版桶排序法，事件復(fù)雜度為O(M+N)，這是一種非?？斓呐判蛩惴?，從1956年開始被使用。但它的缺點(diǎn)是非常的浪費(fèi)空間。
對數(shù)字5 3 5 2 8進(jìn)行排序.png
#include <stdio.h>
int main() {
//定義變量和數(shù)組
int a[11],i,j,t;
//初始化為0
for(i=0;i<11;i++) {
a[i] = 0;
}
//循環(huán)讀入5個(gè)數(shù)
for(i=1;i<=5;i++) {
scanf("%d",&t);
a[t]++;
}
//遍歷每一個(gè)桶，并輸出每一個(gè)桶內(nèi)的東西
//輸出的內(nèi)容就是i
//輸出的次數(shù)就是a[i]此
for(i=0;i<=10;i++) {
for(j=1;j<=a[i];j++) {
printf("%d ",i);
}
}
//使用getchar();暫停程序，以便查看程序的輸出
//你也可以使用 system("pause")進(jìn)行暫停;
getchar();getchar();
return 0;
}
//最初我們使用的是從小到大排序
//如果想要使用從大到小的排序，則將21行的改為 for(i=10;i>=0;i--) 即可
#include <stdio.h>
int main() {
//初始化
int book[1000],i,j,t,n;
for(i=0;i<=1000;i++) { //m次循環(huán)
book[i] = 0;
}
printf("請輸入讀入元素的個(gè)數(shù)：\n");
scanf("%d",&n);
//輸入
for(i=1;i<=n;i++) { //n次循環(huán)
scanf("%d",&t);
book[t]++;
}
//輸出
for(i=0;i<=1000;i++) { //for循環(huán)嵌套 m+n次循環(huán)
for(j=1;j<=book[i];j++) {
printf("%d ",i);
}
}
getchar();getchar();
return 0;
}
//關(guān)鍵要把for循環(huán)嵌套那里的桶概念記清楚
//外圈i是桶的個(gè)數(shù)，也是我們的數(shù)據(jù)
//內(nèi)圈j是元素出現(xiàn)次數(shù)
//事件復(fù)雜度 O(m+n+m+n) => O(2*(m+n)) => O(M+N)
//大O表示法一般都是大寫
//大O表示法一般可以忽略較小的常數(shù)
鄰居好說話——冒泡排序
冒泡排序的基本思想是：每次比較倆個(gè)相鄰的數(shù)字，如果他們順序錯誤，則進(jìn)行交換位置冒泡排序的時(shí)間度是O(N方)，這是一個(gè)非常高的時(shí)間復(fù)雜度。
冒泡排序.png
#include <stdio.h>
int main() {
int a[100],i,j,t,n;
printf("請輸入你要排序的個(gè)數(shù):\n");
scanf("%d",&n);
//存儲玩家輸入的數(shù)字
for(i=0;i<n;i++) {
scanf("%d",&a[i]);
}
//冒泡排序
for(i=0;i<n-1;i++) { //比較n-1躺
for(j=0;j<=n-i;j++) { //每一躺比較的元素個(gè)數(shù)n-i
if(a[j]>a[j+1]) {
t = a[j]; //臨時(shí)存儲a[j]
a[j] = a[j+1];
a[j+1] = t;
}
}
}
//輸出結(jié)果
for(i=0;i<n;i++) {
printf("%d ",a[i]);
}
//暫停程序
getchar();getchar();
return 0;
}
//這里的i和j都是以0開始的，沒有出現(xiàn)數(shù)據(jù)錯誤亂碼的情況
#include <stdio.h>
//結(jié)構(gòu)體
struct student {
char name[100];
int score;
};
int main() {
//初始化變量
struct student a[100],t;
int i,j,n;
//輸入
printf("請輸入你要比較的元素的個(gè)數(shù):");
scanf("%d",&n);
for(i=1;i<=n;i++) {
scanf("%s %d",a[i].name,&a[i].score);
}
//冒泡排序
for(i=1;i<=n-1;i++) {
for(j=1;j<=n-i;j++) {
if(a[j].score>a[j+1].score) {
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
}
}
//輸出
for(i=1;i<=n;i++)
printf("%s ",a[i].name);
//暫停程序
getchar();getchar();
return 0;
}
最常用的排序——快速排序
冒泡排序雖然解決了桶排序的極大浪費(fèi)空間的問題，但是它的算法執(zhí)行效率上卻犧牲了很多，它的時(shí)間復(fù)雜度為O(N方)，假如我們的計(jì)算機(jī)是運(yùn)算次數(shù)是10億/s，那么對1億個(gè)數(shù)進(jìn)行排序，桶排序只需0.1s，而冒泡排序則需要一千萬秒，達(dá)到115天之久，可以使用更加高效的排序算法，快速排序
從右邊開始查找.png
找到并交換值.png
再次找到再次交換.png
i等于j，更新基準(zhǔn)數(shù).png
#include <stdio.h>
//定義全局變量
int a[101],n;
//快速排序
void QuickSort(int left,int right) {
int i,j,t,temp;
if(left>right)
return;
i = left;
j = right;
temp = a[i];
while(i != j) {
//從j開始向左查找
while(a[j]<=temp && i<j)
j--;
//從i開始向右查找
while(a[i]>=temp && i<j) {
i++;
}
if(i<j) {
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
//將基數(shù)歸位
a[left] = a[i];
a[i] = temp;
QuickSort(left,i-1);
QuickSort(i+1,right);
}
int main() {
int i;
printf("請輸入數(shù)據(jù)元素的個(gè)數(shù):\n");
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
QuickSort(1,n);
for(i=1;i<=n;i++) {
printf("%d ",a[i]);
}
getchar();getchar();
return 0;
}
//快速排序是由英國計(jì)算機(jī)科學(xué)家 Tony Hoare 發(fā)明，是一位偉大的英國計(jì)算機(jī)科學(xué)家
//快速排序是分治法的一種思想
//哨兵i,j
//首先，找一個(gè)基準(zhǔn)數(shù)，一般我們把第一個(gè)數(shù)作為基準(zhǔn)數(shù)
//然后，從右邊找一個(gè)小于基準(zhǔn)數(shù)的值并記錄索引的位置，這個(gè)過程是j--
//然后同理從左邊找一個(gè)大于基準(zhǔn)數(shù)的值并記錄索引，這個(gè)過程是i++
//都找到后交換位置
//當(dāng)i=j，交換位置，更新基準(zhǔn)數(shù)
//快速排序最差的情況的它的執(zhí)行效率和冒泡排序一樣都是O(N方),平均時(shí)間復(fù)雜度是O(NlogN)
小哼買書——練習(xí)測試
q1:輸入一串1~1000的整數(shù)，去重且排序，完成后輸出數(shù)據(jù)元素的個(gè)數(shù)。
最終效果.png
思路一：使用改變的桶排序法可以實(shí)現(xiàn)
思路二：使用冒泡先排序，后去重，就是從第二個(gè)開始，比較與前一個(gè)數(shù)是否相等，不相等則輸出
思路三：快速排序，最優(yōu)解法！
總結(jié)：綜上所述，我們的ISBN是在1-1000，范圍太小，如果是-2億~2億呢？或者n接近10萬呢？冒泡排序則需要數(shù)十秒，快速排序則只需要 0.0017s,差距是多么的大，這就是算法的魅力!
//這里只給出桶排序的實(shí)現(xiàn)方法
#include <stdio.h>
int main() {
//j是去重后的元素的個(gè)數(shù)
int a[1000],i,j,t,n;
//初始化數(shù)組
for(i=1;i<1001;i++) {
a[i] = 0;
}
//輸入
printf("請輸入ISBN的總個(gè)數(shù):");
scanf("%d",&n);
//記錄
for(i=1;i<=n;i++) {
scanf("%d",&t);
if(a[t] == 0) {
a[t]++;
j++;
}
}
//輸出
printf("共有%d種不同類型的ISBN號\n",j);
for(i=1;i<=1000;i++) {
if(a[i]>0) {
printf("%d ",i);
}
}
return 0;
}
//桶排序遍歷輸入時(shí)，注意遍歷的是所有的桶，即遍歷所有數(shù)組的索引
棧，隊(duì)列，鏈表
解密QQ號——隊(duì)列
規(guī)則是這樣的：首先將第 1 個(gè)數(shù)刪除，緊接著將第 2 個(gè)數(shù)放到這串?dāng)?shù)的末尾，再將第 3 個(gè)數(shù)刪除并將第 4 個(gè)數(shù)放到這串?dāng)?shù)的末尾，再將第 5 個(gè)數(shù)刪除……直到剩下后一個(gè)數(shù)，將最后一個(gè)數(shù)也刪除。按照剛才刪除的順序，把這些刪除的數(shù)連在一起就是小哈的 QQ 啦。
過程圖.png
#include <stdio.h>
int main() {
int a[102] ={6,3,1,7,5,8,9,2,4},head,tail;
//初始化頭游標(biāo)和尾游標(biāo)
head = 0;
tail = 9;
while(head<tail) {
printf("%d ",a[head]); //輸出第一個(gè)數(shù)
head++; //頭游標(biāo)自增
a[tail]=a[head]; //將第二個(gè)數(shù)移到后邊
tail++; //尾游表自增
head++; //重新一輪
}
getchar();getchar();
return 0;
}
//這個(gè)小算法相當(dāng)于幫助我們了解隊(duì)列的概念
//使用結(jié)構(gòu)體實(shí)現(xiàn)解密QQ號的算法
#include <stdio.h>
//隊(duì)列
struct queue {
int data[100];
int head;
int tail;
};
int main() {
//初始化
struct queue q;
int i;
q.head = 1;
q.tail = 1;
for(i=1;i<=9;i++) {
scanf("%d",&q.data[q.tail]);
q.tail++;
}
while(q.head<q.tail) { //隊(duì)列不為空時(shí)
//刪除數(shù)據(jù)元素
printf("%d ",q.data[q.head]);
q.head++;
//移動數(shù)據(jù)元素
q.data[q.tail] = q.data[q.head];
q.tail++;
q.head++;
}
getchar();getchar();
return 0;
}
使用棧解密回文串
#include <stdio.h>
#include <string.h>
int main() {
//初始化
char a[101],s[101];
int i,len,mid,n,next,top;
//讀入字符串的個(gè)數(shù)
scanf("%d",&n);
//讀入n個(gè)字符并存儲
for(i=1;i<=n;i++) {
scanf("%c",&a[i]);
}
//初始化變量
top = 0;
len = strlen(a);
mid = len/2-1;
//將mid前的數(shù)加入到棧中
for(i=1;i<=mid;i++) {
s[++top]=a[i];
}
//確定mid后next的位置
if(len%2==0)
next = mid + 1;
else
next = mid + 2;
//遍歷從next到結(jié)尾的數(shù)據(jù)比較是否相同
for(i=next;i<=len-1;i++) {
if(a[i] != s[top])
break;
top--;
}
//輸出結(jié)果
if(top == 0)
printf("是回文串");
else
printf("不是回文串");
//暫停程序
getchar();getchar();
//退出程序
return 0;
}
紙牌游戲——小貓釣魚（爬山）
游戲的規(guī)則是這樣的：將一副撲克牌平均分成兩份，每人拿一份。小哼先拿出手的
第一張撲克牌放在桌上，然后小哈也拿出手中的第一張撲克牌，并放在小哼剛打出牌
的上面，就像這樣兩人交替出牌。出牌時(shí)，如果某人打出的牌與桌上某張牌的牌面相同，即可將兩張相同的牌及其中間所夾的牌全部取走，并依次放到自己手中牌尾。任意一人手中的牌全部出完時(shí)，游戲結(jié)束，對手獲勝。
結(jié)果的驗(yàn)證.png
#include <stdio.h>
//模擬我們手牌的隊(duì)列
struct queue {
int data[1000];
int head;
int tail;
};
//模擬桌牌的棧
struct stack {
int data[10];
int top;
};
int main() {
//定義變量
struct queue q1,q2;
struct stack s;
int book[10];
int i,t;
//初始化
q1.head=1;q1.tail=1;
q2.head=1;q2.tail=1;
s.top = 0;
for(i=0;i<=9;i++) {
book[i]=0;
}
//給玩家一發(fā)牌
for(i=1;i<=6;i++) {
scanf("%d",&q1.data[q1.tail]);
q1.tail++;
}
//給玩家二發(fā)牌
for(i=1;i<=6;i++) {
scanf("%d",&q2.data[q2.tail]);
q2.tail++;
}
while(q1.head<q1.tail && q2.head<q2.tail) {
//玩家一出牌
t = q1.data[q1.head];
//判斷玩家一是否可以贏牌
if(book[t]==0) {
//不贏
q1.head++;
s.top++;
s.data[s.top] = t;
book[t] = 1;
}else{
//贏牌
//取得所有贏的牌
/* 我們出的牌 */
q1.head++;
q1.data[q1.tail] = t;
q1.tail++;
/* 中間的牌 */
while(s.data[s.top] != t) {
book[s.data[s.top]] = 0;
q1.data[q1.tail] = s.data[s.top];
q1.tail++;
s.top--;
}
/* 和第一張相同的牌 */
q1.data[q1.tail] = s.data[s.top];
}
//玩家二出牌
t = q2.data[q2.head];
//判斷玩家是否出牌
if(book[t] == 0) {
//沒有贏牌
q2.head++;
s.top++;
s.data[s.top] = t;
book[t] = 1;
}else {
//贏牌
q2.head++;
q2.data[q2.tail] = t;
q2.tail++;
while(s.data[s.top] != t) {
book[s.data[s.top]] = 0;
q2.data[q2.tail] = s.data[s.top];
q2.tail++;
s.top--;
}
q2.data[q2.tail] = s.data[s.top];
}
}
if(q1.head == q1.tail) {
//玩家一輸了
printf("玩家二贏了!\n");
printf("玩家二當(dāng)前的手牌是: ");
for(i=q2.head;i<=q2.tail-1;i++) {
printf("%d ",q2.data[i]);
}
}else {
//玩家二輸了
printf("玩家一贏了!\n");
printf("玩家一的手牌為：");
for(i=q1.head;i<=q1.tail-1;i++) {
printf("%d ",q1.data[i]);
}
}
//如果桌上還有牌
printf("\n");
if(s.top > 0) {
printf("桌上剩余的牌為：");
for(i=1;i<=s.top;i++) {
printf("%d ",s.data[i]);
}
}else {
printf("桌上已經(jīng)沒有牌了!");
}
//暫停程序
getchar();getchar();
//退出程序
return 0;
}
//輸入輸出log為：
//2 4 1 2 5 6
//3 1 3 5 6 4
//玩家一贏了!
//玩家一的手牌為：5 6 2 3 1 4 6 5
//桌上剩余的牌為：2 1 3 4
鏈表
單鏈表的結(jié)構(gòu).png
單鏈表插入結(jié)點(diǎn).png
關(guān)于使用c實(shí)現(xiàn)鏈表需要注意的幾點(diǎn):
t1:怎么分配結(jié)點(diǎn)的內(nèi)存空間，我們使用 (type 星號)malloc(sizeof(dataType)) 來動態(tài)聲明內(nèi)存空間。
t2:因?yàn)槲覀兊墓?jié)點(diǎn)是指針，訪問每一個(gè)節(jié)點(diǎn)的內(nèi)部成員要使用指針運(yùn)算符'->'符號，如p->data=1。
t3:具體實(shí)現(xiàn)代碼會在下面的代碼塊給出。
/*----使用c的結(jié)構(gòu)體+動態(tài)內(nèi)存分配malloc函數(shù)實(shí)現(xiàn)單鏈表----*/
#include <stdio.h>
#include <stdlib.h>
//表示一個(gè)節(jié)點(diǎn)
struct node {
int data;
struct node *next;
};
int main() {
//初始化（頭結(jié)點(diǎn)head,臨時(shí)結(jié)點(diǎn)q,迭代結(jié)點(diǎn)q,遍歷臨時(shí)頭結(jié)點(diǎn)t）
struct node *head,*p,*q,*t;
int i,n,a;
//要讀取幾個(gè)數(shù)
scanf("%d",&n);
//循環(huán)讀入n個(gè)數(shù)
for(i=1;i<=n;i++) {
scanf("%d",&a);
//動態(tài)申請一個(gè)內(nèi)存空間，初始化結(jié)點(diǎn)
p = (struct node *)malloc(sizeof(struct node));
p->data=a;
p->next=NULL;
//判斷頭結(jié)點(diǎn)是否為空
if(head==NULL) {
head=p;
}else{
q->next=p;
}
//更新迭代結(jié)點(diǎn)
q=p;
}
//遍歷單鏈表
t=head;
while(t != NULL) {
printf("%d ",t->data);
t=t->next;
}
//暫停程序
getchar();getchar();
//退出程序
return 0;
}
//打印的日志為
//5
//1 6 6 9 6
//1 6 6 9 6
/*----------接上一節(jié)，實(shí)現(xiàn)單鏈表的插入結(jié)點(diǎn)的操作----------*/
#include <stdio.h>
#include <stdlib.h>
//結(jié)點(diǎn)結(jié)構(gòu)體
struct node {
int data;
struct node *next;
};
int main() {
struct node *head,*p,*q,*t;
int i,n,a;
scanf("%d",&n);
for(i=1;i<=n;i++) {
scanf("%d",&a);
p = (struct node *)malloc(sizeof(struct node));
p->data=a;
p->next=NULL;
if(head==NULL) {
head = p;
}else{
q->next=p;
}
q = p;
}
//單鏈表插入結(jié)點(diǎn)
scanf("%d",&a);
t=head;
while(t != NULL) {
if(t->next->data > a) {
//申請內(nèi)存空間
p = (struct node*)malloc(sizeof(struct node));
p->data=a;
//插入結(jié)點(diǎn)
p->next=t->next;
t->next=p;
break;
}
t=t->next;
}
//遍歷結(jié)點(diǎn)
t=head;
while(t != NULL) {
printf("%d ",t->data);
t=t->next;
}
//暫停程序
getchar();getchar();
//退出程序
return 0;
}
//需要注意的是遍歷所有節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的操作那里，要使用while循環(huán)包上if條件判斷
//置換節(jié)點(diǎn)那里理清思路即可
//測試打印的日志為
//5
//1 3 5 7 9
//6
//1 3 5 6 7 9
模擬鏈表
模擬鏈表的實(shí)現(xiàn)原理圖.png
t1:新插入的數(shù)據(jù)我們直接放在data數(shù)組的后邊即可。
t2:它們之間的關(guān)系我們存儲right數(shù)組中
t3:例如 data[3]右邊的值為data[right[3]]，即data[3]右邊為data[10]
t4:仔細(xì)看一下上面那張圖我們就可以理解。
t5:實(shí)現(xiàn)的代碼在下邊
#include <stdio.h>
int main() {
int data[101],right[101];
int i,n,t,len;
//讀入n個(gè)數(shù)
scanf("%d",&n);
len=n;
//循環(huán)讀入n個(gè)數(shù)
for(i=1;i<=n;i++) {
scanf("%d",&data[i]);
}
//初始化right數(shù)組
for(i=1;i<=n;i++) {
if(i!=n)
right[i]=i+1;
else
right[i]=0;
}
//直接在數(shù)組末尾增加一個(gè)數(shù)
len++;
scanf("%d",&data[len]);
//插入數(shù)據(jù)，更新right數(shù)組
t=1;
while(t!=0) {
if(data[right[t]] > data[len]) {
right[len]=right[t];
right[t]=len;
break;
}
t=right[t];
}
//遍歷數(shù)組
t=1;
while(t!=0) {
printf("%d ",data[t]);
t=right[t];
}
//暫停程序
getchar();getchar();
//退出程序
return 0;
}
//主要是right數(shù)組賦值的邏輯
//right數(shù)組索引保存的是它自身的data數(shù)組的索引，值保存的是它的右邊數(shù)據(jù)的索引
//使用模擬鏈表可以實(shí)現(xiàn)雙向鏈表和循環(huán)鏈表
//打印的日志為
//5
//1 3 5 7 9
//6
//1 3 5 6 7 9
枚舉，很暴力！
坑爹的奧數(shù)
問題圖.png
t1:求像 123 + 456 = 579 這樣的組合有多少種？
t2:我們可以使用暴力枚舉法，遍歷出每種組合？
t3:因?yàn)?456 + 123 = 579 和t1重復(fù)了，所以我們需要將計(jì)算的結(jié)果除2
/*使用暴力枚舉法求解，又叫做窮舉法*/
#include <stdio.h>
int main() {
int a[10],i,total=0,book[10],sum;
for(a[1]=1;a[1]<=9;a[1]++)
for(a[2]=1;a[2]<=9;a[2]++)
for(a[3]=1;a[3]<=9;a[3]++)
for(a[4]=1;a[4]<=9;a[4]++)
for(a[5]=1;a[5]<=9;a[5]++)
for(a[6]=1;a[6]<=9;a[6]++)
for(a[7]=1;a[7]<=9;a[7]++)
for(a[8]=1;a[8]<=9;a[8]++)
for(a[9]=1;a[9]<=9;a[9]++) {
//初始化book數(shù)組
for(i=1;i<=9;i++) {
book[i]=0;
}
//如果某個(gè)數(shù)出現(xiàn)就標(biāo)記一下
for(i=1;i<=9;i++) {
book[a[i]]=1;
}
sum=0;
for(i=1;i<=9;i++) {
sum+=book[i];
}
if(sum==9 && a[1]*100 + a[2]*10 + a[3] + a[4]*100 + a[5]*10 + a[6] == a[7]*100 + a[8]*10 + a[9]) {
total++;
printf("%d%d%d+%d%d%d=%d%d%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
}
}
printf("total=%d",total/2);
getchar();getchar();
return 0;
}
炸彈人
炸彈人游戲.png
上下左右遍歷.png
t1:給出一個(gè)二維的數(shù)組模擬我們的整個(gè)地圖
t2:使用 "#" 表示墻， "." 表示空地， "G" 表示敵人
t3:如是是向上遍歷地圖，則是y不變x--,可以結(jié)合上圖看
t4:請寫出相關(guān)的算法，算出將炸彈放在哪個(gè)位置炸死的敵人最多
#include <stdio.h>
int main() {
//地圖大小不超過20*20
char a[20][20];
//初始化變量
int i,j,sum,map=0,p,q,x,y,n,m;
scanf("%d %d",&n,&m);
//讀入n行字符,每行讀取20個(gè)以內(nèi)的字符
for(i=0;i<=n-1;i++) {
scanf("%s",a[i]);
}
//雙層for循環(huán)枚舉所有地形
for(i=0;i<=n-1;i++) {
for(j=0;j<=n-1;j++) {
//如果是空地，才可以放置炸彈
if(a[i][j] == '.') {
//可以殺死的敵人的數(shù)量
sum=0;
//將當(dāng)前遍歷的格子存儲在臨時(shí)變量x和y中
x=i;y=j;
//向上統(tǒng)計(jì)可以消滅敵人的數(shù)量
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
x--;
}
//向下統(tǒng)計(jì)可以消滅敵人的數(shù)量
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
x++;
}
//向左統(tǒng)計(jì)可以消滅敵人的數(shù)量
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
y--;
}
//向右統(tǒng)計(jì)可以消滅敵人的數(shù)量
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
y++;
}
if(sum>map) {
//更新和記錄能消滅敵人的最大數(shù)量
map=sum;
//同時(shí)更新坐標(biāo)(哪行哪列)
p=i;
q=j;
}
}
}
}
printf("將炸彈放置在%d行%d列，最多可以消滅%d個(gè)敵人",p,q,map);
getchar();getchar();
return 0;
}
//輸入和輸出為
//13 13
//#############
//#GG.GGG#GGG.#
//###.#G#G#G#G#
//#.......#..G#
//#G#.###.#G#G#
//#GG.GGG.#.GG#
//#G#.#G#.#.###
//##G...G.....#
//#G#.#G###.#G#
//#...G#GGG.GG#
//#G#.#G#G#.#G#
//#GG.GGG#G.GG#
//#############
//將炸彈放置在9行9列，最多可以消滅8個(gè)敵人
火柴棍等式
每個(gè)數(shù)字需要用到的火柴棍的個(gè)數(shù).png
t1:加號和等于號各需要2根火柴棍
t2:如果a不等于b，a+b=c 和 b+a=c 視為不同的等式(a,b,c都大于0)
t3:所有火柴棍必須都用上，假設(shè)有火柴棍24個(gè)，即24-4=20個(gè)
t4:假如某人有m根火柴，那么究竟可以拼出多少個(gè)a+b=c的等式
t5:設(shè)計(jì)求解算法，要求時(shí)間復(fù)雜度為O(N方)
#include <stdio.h>
//得到一個(gè)數(shù)字的火柴的個(gè)數(shù)
int fun(int x) {
//記錄已經(jīng)使用的火柴的數(shù)量
int num=0;
//記錄0~9數(shù)字的火柴棍的個(gè)數(shù)
int f[10] = {6,2,5,5,4,5,6,3,7,6};
//如果x不是一位數(shù)
while(x/10!=0) {
//獲得末尾的數(shù)字的火柴的個(gè)數(shù)
num+=f[x%10];
//取出末尾的數(shù)字
x/=10;
}
//出了上面的while循環(huán),x必定是一位數(shù)
num+=f[x];
//返回火柴的總個(gè)數(shù)
return num;
}
int main() {
//初始化變量
int a,b,c,m,i,sum=0; //sum是用來計(jì)數(shù)的，因此一定要初始化為0
//讀入火柴棍的個(gè)數(shù)，存儲在m變量中
scanf("%d",&m);
//開始枚舉a和b
for(a=0;a<=1111;a++) {
for(b=0;b<=1111;b++) {
//算a+b的和
c=a+b;
//如果滿足條件
if(fun(a)+fun(b)+fun(c)==m-4) {
printf("%d+%d=%d\n",a,b,c);
sum++;
}
}
}
printf("一共可以拼出%d個(gè)不同的等式",sum);
//暫停程序
getchar();getchar;
//結(jié)束程序
return 0;
}
//要枚舉a b c,就要想到三個(gè)數(shù)值的范圍是0~1111之間
//那么接下來只需要暴力枚舉這之間的數(shù)判斷篩選即可
//輸入和輸出的結(jié)果為
//18
//0+4=4
//0+11=11
//1+10=11
//2+2=4
//2+7=9
//4+0=4
//7+2=9
//10+1=11
//11+0=11
//一共可以拼出9個(gè)不同的等式
數(shù)的全排列
數(shù)字123的全排列.png
t1:請?jiān)O(shè)計(jì)一個(gè)算法，實(shí)現(xiàn)1234的數(shù)字的全排列
t2:我們可以使用四層for循環(huán)嵌套篩選和過濾出滿足 a!=b a!=c a!=d b!=c b!=d c!=d的排列
t3:具體實(shí)現(xiàn)代碼如下圖
//求1234的數(shù)的全排列組合
//并輸出一共有多少種這樣的組合
#include <stdio.h>
int main() {
//求1234的數(shù)的全排列
int a,b,c,d,sum=0;
for(a=1;a<=4;a++)
for(b=1;b<=4;b++)
for(c=1;c<=4;c++)
for(d=1;d<=4;d++) {
if(a!=b && a!=c && a!=d && b!=c && b!=d && c!=d) {
printf("%d%d%d%d\n",a,b,c,d);
sum++;
}
}
printf("一共有%d種排列",sum);
getchar();getchar();
return 0;
}
//輸出為
//1234
//1243
//1324
//1342
//1423
//1432
//2134
//2143
//2314
//2341
//2413
//2431
//3124
//3142
//3214
//3241
//3412
//3421
//4123
//4132
//4213
//4231
//4312
//4321
//一共有24種排列
深度優(yōu)先搜索
用深度優(yōu)先的思想解決數(shù)的全排列
t1:接上邊的那個(gè)算法
t2:輸入3,就是求123的全排列，4就是1234的全排列，(0<n<9)
#include <stdio.h>
int a[10],book[10],n;
void dfs(int step) { //step表示我們當(dāng)前在第幾個(gè)盒子面前
int i;
if(step==n+1) {
for(i=1;i<=n;i++) {
printf("%d",a[i]);
}
printf("\n");
return;
}
//此時(shí)站在第step個(gè)盒子面前，要考慮放哪張牌的問題
for(i=1;i<=n;i++) {
if(book[i]==0) {
a[step]=i;
book[i]=1;
dfs(step+1);
book[i]=0;
}
}
return;
}
int main() {
scanf("%d",&n);
dfs(1);
getchar();getchar();
return 0;
}
//輸出和輸出的結(jié)果為
//3
//123
//132
//213
//231
//312
//321
用深度優(yōu)先解決之前的數(shù)字填空的問題
即 口口口+口口口=口口口 這種問題
#include <stdio.h>
int a[10],book[10],n;
//封裝到每一個(gè)箱子面前要進(jìn)行的步驟
void dfs(int step) {
int i;
if(step==n+1) {
if((a[1]*100+a[2]*10+a[3]) + (a[4]*100+a[5]*10+a[6]) == (a[7]*100+a[8]*10+a[9])) {
printf("%d%d%d+%d%d%d=%d%d%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
}
return;
}
for(i=1;i<=9;i++) {
if(book[i]==0) {
a[step]=i;
book[i]=1;
dfs(step+1);
book[i]=0;
}
}
return;
}
int main() {
//表示有幾個(gè)箱子，其實(shí)就是數(shù)字一共有9為，如123+456=579
n=9;
//從第一個(gè)箱子開始
dfs(1);
//暫停程序
getchar();getchar();
//退出程序
return 0;
}
解救小哈
要走的四個(gè)方向的關(guān)系變化圖.png
t1:使用深度優(yōu)先搜索找到最段路徑
t2:遍歷查找的方向依次為右下左上(順時(shí)針)查找，這里我們使用了一個(gè)int[4][2]的二維數(shù)組
t3:具體的實(shí)現(xiàn)的代碼如下
/*使用深度優(yōu)先的算法求倆點(diǎn)的最短路徑*/
#include <stdio.h>
//初始化全局變量
int n,m,p,q,min=99999999;
int a[51][51],book[51][51];
void dfs(int x,int y,int step) {
//定義一個(gè)二維的數(shù)組存儲存儲我們要搜索的方向
int next[4][2] = {{0,1}, //向右搜索
{1,0}, //向下搜索
{0,-1}, //向左搜索
{-1,0}}; //向上搜索
int tx,ty,k;
//判斷是否到達(dá)小哈的位置
if(x==p && y==q) {
if(step<min) {
min=step;
return;
}
}
//枚舉四種走法
for(k=0;k<=3;k++) {
//計(jì)算下一個(gè)方向
tx=x+next[k][0];
ty=y+next[k][1];
//如果越界，就直接進(jìn)行計(jì)算下一個(gè)方向
if(tx<1 || tx>n || ty<1 || ty>m)
continue;
//判斷該店是否為障礙物且已經(jīng)在路徑中
if(a[tx][ty]==0 && book[tx][ty]==0) {
//標(biāo)記這個(gè)點(diǎn)為已經(jīng)走過
book[tx][ty]=1;
//嘗試下一個(gè)點(diǎn)
dfs(tx,ty,step+1);
//嘗試結(jié)束，取消這個(gè)點(diǎn)的標(biāo)記
book[tx][ty]=0;
}
}
return;
}
int main() {
//初始化變量
int i,j,startx,starty;
//讀入n和m,n為行，m為列
scanf("%d %d",&n,&m);
//讀入迷宮
for(i=1;i<=n;i++) {
for(j=1;j<=m;j++) {
scanf("%d",&a[i][j]);
}
}
//讀入起點(diǎn)和終點(diǎn)
scanf("%d %d %d %d",&startx,&starty,&p,&q);
//從起點(diǎn)開始走
book[startx][starty]=1;
dfs(startx,starty,0);
//輸出最短步數(shù)
printf("解救小哈的最短步數(shù)為%d",min);
getchar();getchar();
return 0;
}
廣度優(yōu)先搜索
解救小哈
t1:我們之前使用了深度優(yōu)先搜索，查找了小哈到小哼的步數(shù)
t2:這一接我們使用寬度優(yōu)先搜索的方法
t3:實(shí)現(xiàn)的代碼如下
#include <stdio.h>
//結(jié)點(diǎn)結(jié)構(gòu)體
struct note {
int x; //橫坐標(biāo)
int y; //縱坐標(biāo)
int f; //父親在隊(duì)列中的編號
int s; //步數(shù)
};
int main() {
struct note queue[2501]; //隊(duì)列
//存儲地圖的二位數(shù)組和book標(biāo)記數(shù)組
int a[51][51] = {0};
int book[51][51] = {0};
//定義一個(gè)方向的數(shù)組，依次是右下左上
int next[4][2] = {{0,1},
{1,0},
{0,-1},
{-1,0}};
//隊(duì)列的頭尾標(biāo)記
int head,tail;
//初始化各種變量
int i,j,k,n,m,startx,starty,p,q,tx,ty,flag;
//輸入行列的信息
scanf("%d %d",&n,&m);
//初始化二維數(shù)組
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&a[i][j]);
//輸入起點(diǎn)和終點(diǎn)
scanf("%d %d %d %d",&startx,&starty,&p,&q);
//隊(duì)列的初始化
head=1;
tail=1;
//往隊(duì)列插入起點(diǎn)
queue[tail].x = startx;
queue[tail].y = starty;
queue[tail].f = 0;
queue[tail].s = 0;
tail++;
//標(biāo)記起點(diǎn)為已走過
book[startx][starty] = 1;
//flag為0未找到終點(diǎn)，1則是找到
flag = 0;
//當(dāng)隊(duì)列不為空
while(head<tail) {
for(k=0;k<=3;k++) {
//計(jì)算下一個(gè)點(diǎn)的位置
tx=queue[head].x+next[k][0];
ty=queue[head].y+next[k][1];
//校驗(yàn)
if(tx<1 || tx>n || ty<1 || ty>m)
continue;
//如果這個(gè)點(diǎn)為0即空地且未被標(biāo)記
if(a[tx][ty]==0 && book[tx][ty]==0) {
//滿足條件，加入到隊(duì)列中
book[tx][ty] = 1;
queue[tail].x = tx;
queue[tail].y = ty;
queue[tail].f = head;
queue[tail].s = queue[head].s+1;
tail++;
}
//判斷是否到達(dá)終點(diǎn)
if(tx==p && ty==q) {
flag=1;
break;
}
}
if(flag==1)
break;
head++;
}
//輸出到目標(biāo)點(diǎn)一共走了多少步
printf("從小哈到小哼一共走了%d步",queue[tail-1].s);
//暫停程序
getchar();getchar();
//退出程序
return 0;
}
//輸入和輸出為
//5 4
//0 0 1 0
//0 0 0 0
//0 0 1 0
//0 1 0 0
//0 0 0 1
//1 1 4 3
//從小哈到小哼一共走了7步
使用廣搜再解炸彈人
t1:這次我們解決了炸彈人不可以走在炸彈上的問題
t2:使用的是廣度優(yōu)先搜索
t3:關(guān)于二維字符數(shù)字的賦值我們這里可以使用下面的方式，給一個(gè)for循環(huán)，里面加上scanf("%s",a[i]);這樣
t4:上面表示接受了多少行字符，不用加取地址符&
t5:具體代碼如下
#include <stdio.h>
//表示一個(gè)位置結(jié)點(diǎn)
struct node {
int x;
int y;
};
char a[20][21];
//求炸彈可以消滅敵人的數(shù)量
int getnum(int i,int j) {
int sum,x,y;
sum=0;
//向上搜索
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y]=='G') {
sum++;
}
x--;
}
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y]=='G') {
sum++;
}
x++;
}
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
y--;
}
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
y++;
}
return sum;
}
int main() {
struct node queue[401];
int book[20][20]={0};
int head;
int tail;
int startx,starty,mx,my,tx,ty,sum,max=0,n,m,i,j,k;
//四個(gè)方向
int next[4][2]={{0,1},
{1,0},
{0,-1},
{-1,0}};
scanf("%d %d %d %d",&n,&m,&startx,&starty);
for(i=0;i<=n-1;i++)
scanf("%s",a[i]);
head=1;
tail=1;
queue[tail].x=startx;
queue[tail].y=starty;
tail++;
book[startx][starty] = 1;
max=getnum(startx,starty);
mx=startx;
my=starty;
while(head<tail) {
for(k=0;k<=3;k++) {
//求出下一個(gè)要搜索的位置結(jié)點(diǎn)
tx=queue[head].x+next[k][0];
ty=queue[head].y+next[k][1];
//判斷這個(gè)位置是否符合要求
if(tx<0 || tx>n-1 || ty<0 || ty>m-1)
continue;
if(a[tx][ty]=='.' && book[tx][ty]==0) {
book[tx][ty]=1;
queue[tail].x=tx;
queue[tail].y=ty;
tail++;
sum=getnum(tx,ty);
if(sum>max) {
//更新最小值min和記錄結(jié)點(diǎn)的位置
max=sum;
mx=tx;
my=ty;
}
}
}
head++;
}
printf("將炸彈人放在(%d,%d)個(gè)位置上，最多可以消滅%d個(gè)敵人",mx,my,max);
getchar();getchar();
return 0;
}
//輸入和輸出為
//13 13 3 3
//#############
//#GG.GGG#GGG.#
//###.#G#G#G#G#
//#.......#..G#
//#G#.###.#G#G#
//#GG.GGG.#.GG#
//#G#.#G#.#.#.#
//##G...G.....#
//#G#.#G###.#G#
//#...G#GGG.GG#
//#G#.#G#G#.#G#
//#GG.GGG#G.GG#
//#############
//將炸彈人放在(7,11)個(gè)位置上，最多可以消滅10個(gè)敵人
使用深搜再解炸彈人
t1:思路就是使用深度優(yōu)先遍歷的方法，遍歷每一個(gè)點(diǎn)，最后會記錄的一個(gè)點(diǎn)的位置，這個(gè)位置炸死的敵人的數(shù)量是最多的
t2:只需要把dfs的每一步做好就行，在每一個(gè)點(diǎn)進(jìn)行遍歷，計(jì)算炸死的敵人的數(shù)量即可
t3:實(shí)現(xiàn)代碼如下
#include <stdio.h>
//定義標(biāo)志和地圖的二維數(shù)組
char a[20][21];
int book[20][20],max=0,mx,my,n,m;
//得到可以消滅的敵人的數(shù)量
int getnum(int i,int j) {
//炸死的敵人的數(shù)量
int sum,x,y;
sum = 0;
//向上搜索
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
x--;
}
//向下搜索
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
x++;
}
//向左搜索
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
y--;
}
//向右搜索
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
y++;
}
//返回得到的炸彈數(shù)
return sum;
}
//每一步遞歸要進(jìn)行的操作
void dfs(int x,int y) {
//定義一個(gè)用戶表示方向的數(shù)組
int next[4][2] = {{0,1},
{1,0},
{0,-1},
{-1,0}};
int k,sum,tx,ty;
sum=getnum(x,y);
if(sum>max) {
max=sum;
mx=x;
my=y;
}
for(k=0;k<=3;k++) {
//計(jì)算下一個(gè)要遍歷的點(diǎn)
tx=x+next[k][0];
ty=y+next[k][1];
if(tx<0 || tx>n-1 || ty<0 || ty>m-1)
continue;
if(a[tx][ty]=='.' && book[tx][ty]==0) {
book[tx][ty]=1;
dfs(tx,ty);
}
}
return;
}
int main() {
//初始化變量
int i,j,startx,starty;
//讀入有多少行和多少列
scanf("%d %d %d %d",&n,&m,&startx,&starty);
//讀入n行字符
for(i=0;i<=n-1;i++)
scanf("%s",a[i]);
book[startx][starty]=1;
max=getnum(startx,starty);
mx=startx;
my=starty;
dfs(startx,starty);
//輸出結(jié)果
printf("將炸彈放在(%d,%d)個(gè)位置，最多可以消滅%d個(gè)敵人",mx,my,max);
//暫停程序
getchar();getchar();
//退出程序
return 0;
}
//輸入和輸出的結(jié)果為
//13 13 3 3
//#############
//#GG.GGG#GGG.#
//###.#G#G#G#G#
//#.......#..G#
//#G#.###.#G#G#
//#GG.GGG.#.GG#
//#G#.#G#.#.#.#
//##G...G.....#
//#G#.#G###.#G#
//#...G#GGG.GG#
//#G#.#G#G#.#G#
//#GG.GGG#G.GG#
//#############
//將炸彈放在(7,11)個(gè)位置，最多可以消滅10個(gè)敵人
寶島探險(xiǎn)
使用廣搜解決島嶼的面積的問題
寶島探險(xiǎn).png
t1:有一個(gè)10*10大小的二維矩陣是一個(gè)寶島的航拍地圖，使用數(shù)字0代表海洋，使用數(shù)字1~9代表陸地
t2:現(xiàn)在假設(shè)小哼要降落在某個(gè)島上并算出這個(gè)島的面積
t3:我們可以使用廣度優(yōu)先搜索方法解決這個(gè)問題
t4:頂一個(gè)一個(gè)變量，遍歷每一個(gè)格子，如果是大于1， 變量就進(jìn)行自增
t5:最后輸出這個(gè)變量就是這個(gè)島嶼的面積
#include <stdio.h>
//0海洋 1~9表示陸地
//格子不超過50*50
//表示一個(gè)結(jié)點(diǎn)
struct node {
int x;
int y;
};
int main() {
//初始化
struct node queue[2501];
int a[51][51];
int book[51][51];
int n,m,i,j,k,tx,ty,startx,starty,head,tail,sum;
scanf("%d %d %d %d",&n,&m,&startx,&starty);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&a[i][j]);
head=1;
tail=1;
//把小哼降落的位置加入到隊(duì)列
queue[head].x=startx;
queue[head].y=starty;
tail++;
book[startx][starty]=1;
sum=1;
//要遍歷的四個(gè)方向
int next[4][2]={{0,1},
{1,0},
{0,-1},
{-1,0}};
//隊(duì)列不為空
while(head<tail) {
for(k=0;k<=3;k++) {
tx=queue[head].x+next[k][0];
ty=queue[head].y+next[k][1];
if(tx<1 || tx>n || ty<1 || ty>m)
continue;
if(a[tx][ty]>0 && book[tx][ty]==0) {
sum++;
book[tx][ty]=1;
queue[tail].x=tx;
queue[tail].y=ty;
tail++;
}
}
head++;
}
//輸出
printf("該島嶼的面積為%d",sum);
getchar();getchar();
return 0;
}
//輸入和輸出為
//10 10 6 8
//1 2 1 0 0 0 0 0 2 3
//3 0 2 0 1 2 1 0 1 2
//4 0 1 0 1 2 3 2 0 1
//3 2 0 0 0 1 2 4 0 0
//0 0 0 0 0 0 1 5 3 0
//0 1 2 1 0 1 5 4 3 0
//0 1 2 3 1 3 6 2 1 0
//0 0 3 4 8 9 7 5 0 0
//0 0 0 3 7 8 6 0 1 2
//0 0 0 0 0 0 0 0 1 0
//該島嶼的面積為38
使用廣搜解決島嶼的面積的問題(接上一節(jié))
#include <stdio.h>
int a[51][51];
int book[51][51];
int n,m,sum=0;
void dfs(int x,int y) {
int next[4][2]={{0,1},
{1,0},
{0,-1},
{-1,0}};
int tx,ty,k;
for(k=0;k<=3;k++) {
//計(jì)算下一個(gè)點(diǎn)
tx=x+next[k][0];
ty=y+next[k][1];
if(tx<1 || tx>n || ty<1 || tx>m)
continue;
if(a[tx][ty]>0 && book[tx][ty]==0) {
sum++;
book[tx][ty]=1;
dfs(tx,ty);
}
}
return;
}
int main() {
int i,j,startx,starty;
scanf("%d %d %d %d",&n,&m,&startx,&starty);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&a[i][j]);
sum=1;
book[startx][starty]=1;
dfs(startx,starty);
printf("小島的面積為%d",sum);
getchar();getchar();
return 0;
}
//輸出和輸入同上一節(jié)
寶島探險(xiǎn)添加參數(shù)color
t1:只是給遞歸函數(shù)dfs添加了一個(gè)新的int類型參數(shù)color
t2:就是將小哼降落的小島染色
#include <stdio.h>
int a[51][51];
int book[51][51],n,m,sum;
void dfs(int x,int y,int color) {
int k,tx,ty;
//四個(gè)方向
int next[4][2]={{0,1},
{1,0},
{0,-1},
{-1,0}};
a[x][y]=color;
for(k=0;k<=3;k++) {
tx=x+next[k][0];
ty=y+next[k][1];
if(tx<1 || tx>n || ty<1 || ty>m)
continue;
if(a[tx][ty]>0 && book[tx][ty]==0) {
book[tx][ty]=1;
dfs(tx,ty,color);
}
}
//這個(gè)return可以忽略不加
return;
}
int main() {
int i,j,startx,starty;
scanf("%d %d %d %d",&n,&m,&startx,&starty);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&a[i][j]);
dfs(startx,starty,-1);
for(i=1;i<=n;i++) {
for(j=1;j<=m;j++) {
printf("%3d",a[i][j]);
}
printf("\n");
}
getchar();getchar();
return 0;
}
//輸入和輸出為
//10 10 6 8
//1 2 1 0 0 0 0 0 2 3
//3 0 2 0 1 2 1 0 1 2
//4 0 1 0 1 2 3 2 0 1
//3 2 0 0 0 1 2 4 0 0
//0 0 0 0 0 0 1 5 3 0
//0 1 2 1 0 1 5 4 3 0
//0 1 2 3 1 3 6 2 1 0
//0 0 3 4 8 9 7 5 0 0
//0 0 0 3 7 8 6 0 1 2
//0 0 0 0 0 0 0 0 1 0
//1 2 1 0 0 0 0 0 2 3
//3 0 2 0 -1 -1 -1 0 1 2
//4 0 1 0 -1 -1 -1 -1 0 1
//3 2 0 0 0 -1 -1 -1 0 0
//0 0 0 0 0 0 -1 -1 -1 0
//0 -1 -1 -1 0 -1 -1 -1 -1 0
//0 -1 -1 -1 -1 -1 -1 -1 -1 0
//0 0 -1 -1 -1 -1 -1 -1 0 0
//0 0 0 -1 -1 -1 -1 0 1 2
//0 0 0 0 0 0 0 0 1 0
寶島探險(xiǎn)求得海洋上小島的個(gè)數(shù)
t1:思路還是使用深度優(yōu)先搜索
t2:改變的只是添加了一個(gè)num參數(shù)，每次找到一個(gè)小島的一部分，num--即可
t3:使用深度優(yōu)先搜索遞歸完成之后，輸出num的值即可
t4:這里思維較容易混亂，要注意區(qū)分最后使用遞歸找小島的dfs和num之間關(guān)系的區(qū)分
#include <stdio.h>
int a[51][51];
int book[51][51],n,m,sum;
//深度優(yōu)先遍歷的遞歸調(diào)用
void dfs(int x,int y,int color) {
int next[4][2] = {{0,1}, //右邊
{1,0}, //下邊
{0,-1}, //左邊
{-1,0}}; //上邊
int k,tx,ty;
//將這個(gè)格子進(jìn)行染色
a[x][y]=color;
//枚舉四個(gè)方向
for(k=0;k<=3;k++) {
tx=x+next[k][0];
ty=y+next[k][1];
if(tx<1 || tx>n || ty<1 || ty>m)
continue;
if(a[tx][ty]>0 && book[tx][ty]==0) {
sum++;
book[tx][ty]=1;
dfs(tx,ty,color);
}
}
}
int main() {
//初始化變量
int i,j,num=0;
//輸入小島的行列和連接信息
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++) {
for(j=1;j<=m;j++) {
scanf("%d",&a[i][j]);
}
}
//遞歸計(jì)算一共有幾個(gè)小島
for(i=1;i<=n;i++) {
for(j=1;j<=m;j++) {
if(a[i][j]>0) {
num--;
book[i][j]=1;
dfs(i,j,num);
}
}
}
//輸出小島信息
for(i=1;i<=n;i++) {
for(j=1;j<=m;j++) {
printf("%3d",a[i][j]);
}
printf("\n");
}
printf("一共有%d個(gè)小島",-num);
getchar();getchar();
return 0;
}
//輸入和輸出分別是
//10 10
//1 2 1 0 0 0 0 0 2 3
//3 0 2 0 1 2 1 0 1 2
//4 0 1 0 1 2 3 2 0 1
//3 2 0 0 0 1 2 4 0 0
//0 0 0 0 0 0 1 5 3 0
//0 1 2 1 0 1 5 4 3 0
//0 1 2 3 1 3 6 2 1 0
//0 0 3 4 8 9 7 5 0 0
//0 0 0 3 7 8 6 0 1 2
//0 0 0 0 0 0 0 0 1 0
// -1 -1 -1 0 0 0 0 0 -2 -2
// -1 0 -1 0 -3 -3 -3 0 -2 -2
// -1 0 -1 0 -3 -3 -3 -3 0 -2
// -1 -1 0 0 0 -3 -3 -3 0 0
// 0 0 0 0 0 0 -3 -3 -3 0
// 0 -3 -3 -3 0 -3 -3 -3 -3 0
// 0 -3 -3 -3 -3 -3 -3 -3 -3 0
// 0 0 -3 -3 -3 -3 -3 -3 0 0
// 0 0 0 -3 -3 -3 -3 0 -4 -4
// 0 0 0 0 0 0 0 0 -4 0
//一共有4個(gè)小島
水管工游戲
水管工游戲.png水管連通之后.png每個(gè)數(shù)字代表不同的水管.png
t1:0代表樹木，1-6代表管子（1-4是彎管，5和6是直的管子）
t2:輸入矩陣的行列信息
t3:輸入每條管道的信息
t4:輸出是否可以構(gòu)成一條連通的管道
#include <stdio.h>
int a[51][51];
int book[51][51],n,m,flag=0;
void dfs(int x,int y,int front) {
if(x==n && y==m+1) {
flag=1;
return;
}
//判斷是否越界
if(x<1 || x>n || y<1 || y>m)
return;
//判斷管道是否在游戲中使用過
if(book[x][y]==1)
return;
//標(biāo)記這個(gè)管道已經(jīng)遍歷過
book[x][y]=1;
//當(dāng)前水管是直管的時(shí)候
if(a[x][y]>=5 && a[x][y]<=6) {
//進(jìn)水口在左邊
if(front==1) {
dfs(x,y+1,1);
}
//進(jìn)水口在上邊
if(front==2) {
dfs(x+1,y,2);
}
//進(jìn)水口在右邊
if(front==3) {
dfs(x,y-1,3);
}
//進(jìn)水口在下邊
if(front==4) {
dfs(x-1,y,4);
}
}
if(a[x][y]>=1 && a[x][y]<=4) {
if(front==1) {
dfs(x+1,y,2);
dfs(x-1,y,4);
}
if(front==2) {
dfs(x,y+1,1);
dfs(x,y-1,3);
}
if(front==3) {
dfs(x+1,y,2);
dfs(x-1,y,4);
}
if(front==4) {
dfs(x,y+1,1);
dfs(x,y-1,3);
}
}
//如果有管子可以連接下去，就會一直遞歸調(diào)用，否則就會執(zhí)行下面這個(gè)操作返回到上一次的地方
//這里是個(gè)難點(diǎn)，也是區(qū)分于廣度優(yōu)先搜索的代碼
book[x][y]=0;
return;
}
int main() {
int i,j,num=0;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++) {
for(j=1;j<=m;j++) {
scanf("%d",&a[i][j]);
}
}
dfs(1,1,1);
if(flag==0) {
printf("impossible\n");
}else{
printf("找到鋪設(shè)方案\n");
}
getchar();getchar();
return 0;
}
//輸入和輸出是
//5 4
//5 3 5 3
//1 5 3 0
//2 3 5 1
//6 1 1 5
//1 5 5 4
//找到鋪設(shè)方案
水管工游戲保存和輸出路徑點(diǎn)
t1:就是添加了一個(gè)結(jié)構(gòu)體和結(jié)構(gòu)體的數(shù)組
t2:添加了一個(gè)新的標(biāo)志位top，默認(rèn)為0
#include <stdio.h>
struct node {
int x;
int y;
}s[100];
int a[51][51];
int book[51][51],n,m,flag=0;
int top=0;
void dfs(int x,int y,int front) {
int k;
if(x==n && y==m+1) {
flag=1;
for(k=1;k<=top;k++) {
printf("(%d,%d)",s[k].x,s[k].y);
}
return;
}
//判斷是否越界
if(x<1 || x>n || y<1 || y>m)
return;
//判斷管道是否在游戲中使用過
if(book[x][y]==1)
return;
//標(biāo)記這個(gè)管道已經(jīng)遍歷過
book[x][y]=1;
top++;
s[top].x=x;
s[top].y=y;
//當(dāng)前水管是直管的時(shí)候
if(a[x][y]>=5 && a[x][y]<=6) {
//進(jìn)水口在左邊
if(front==1) {
dfs(x,y+1,1);
}
//進(jìn)水口在上邊
if(front==2) {
dfs(x+1,y,2);
}
//進(jìn)水口在右邊
if(front==3) {
dfs(x,y-1,3);
}
//進(jìn)水口在下邊
if(front==4) {
dfs(x-1,y,4);
}
}
if(a[x][y]>=1 && a[x][y]<=4) {
if(front==1) {
dfs(x+1,y,2);
dfs(x-1,y,4);
}
if(front==2) {
dfs(x,y+1,1);
dfs(x,y-1,3);
}
if(front==3) {
dfs(x+1,y,2);
dfs(x-1,y,4);
}
if(front==4) {
dfs(x,y+1,1);
dfs(x,y-1,3);
}
}
book[x][y]=0;
top--;
return;
}
int main() {
int i,j,num=0;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++) {
for(j=1;j<=m;j++) {
scanf("%d",&a[i][j]);
}
}
dfs(1,1,1);
if(flag==0) {
printf("impossible\n");
}
getchar();getchar();
return 0;
}
//輸入和輸出為:
//5 4
//5 3 5 3
//1 5 3 0
//2 3 5 1
//6 1 1 5
//1 5 5 4
//(1,1)(1,2)(2,2)(3,2)(3,3)(3,4)(4,4)(5,4)
再探深度優(yōu)先搜索
我們要遍歷的圖.png
使用鄰接矩陣存儲邊.png
圖的頂點(diǎn)的訪問順序.png
t1:本題要求使用深度優(yōu)先搜索遍歷所有頂點(diǎn)并輸出頂點(diǎn)
t2:圖三是使用深度優(yōu)先搜索遍歷輸出頂點(diǎn)的順序，頂點(diǎn)旁邊的數(shù)字我們叫做事件戳
t3:實(shí)現(xiàn)代碼如下
#include <stdio.h>
//初始化變量
int book[101],e[101][101],sum=0,n,inf=99999999;
//深度優(yōu)先搜索
void dfs(int cur) {
//初始化變量并輸出當(dāng)前遍歷的點(diǎn)
int i;
printf("%d ",cur);
sum++;
if(sum==n)
return;
//檢查是否有邊的連接
for(i=1;i<=n;i++) {
if(e[cur][i]==1 && book[i]==0) {
book[i]=1;
dfs(i);
}
}
return;
}
int main() {
int m,i,j,a,b;
//n是頂點(diǎn)的個(gè)數(shù)，m的邊的個(gè)數(shù)
scanf("%d %d",&n,&m);
//初始化二維數(shù)組
for(i=1;i<=n;i++) {
for(j=1;j<=n;j++) {
if(i==j){
e[i][j]=0;
}else{
e[i][j]=inf;
}
}
}
//輸入邊的信息并存儲，注意這里是無向圖
for(i=1;i<=m;i++) {
scanf("%d %d",&a,&b);
e[a][b]=1;
e[b][a]=1;
}
//從一號頂點(diǎn)開始深度優(yōu)先搜索
book[1]=1;
dfs(1);
getchar();getchar();
return 0;
}
//輸入和輸出為
//5 5
//1 2
//1 3
//1 5
//3 5
//2 4
//1 2 4 3 5
使用廣度優(yōu)先搜索遍歷上一節(jié)的圖
t1:遍歷方式改為廣搜，實(shí)現(xiàn)的代碼如下
#include <stdio.h>
//初始化相關(guān)變量
int queue[101],book[101],e[101][101],inf=99999999;
int main() {
int n,m,i,j,a,b,cur;
int head,tail;
//n是頂點(diǎn)個(gè)數(shù)，m是邊的個(gè)數(shù)
scanf("%d %d",&n,&m);
//初始化二維數(shù)組
for(i=1;i<=n;i++) {
for(j=1;j<=n;j++) {
if(i==j) {
e[i][j]=0;
}else{
e[i][j]=inf;
}
}
}
//使用鄰接矩陣存儲邊
for(i=1;i<=m;i++) {
scanf("%d %d",&a,&b);
e[a][b]=1;
e[b][a]=1;
}
//初始化隊(duì)列的頭尾節(jié)點(diǎn)
head=1;
tail=1;
//將第一個(gè)頂點(diǎn)添加到隊(duì)列中
queue[tail]=1;
tail++;
book[1]=1;
//當(dāng)隊(duì)列不為空
while(head<tail) {
//當(dāng)前藥遍歷的根節(jié)點(diǎn)
cur=queue[head];
//遍歷所有節(jié)點(diǎn)
for(i=1;i<=n;i++) {
if(e[cur][i]==1 && book[i]==0) {
queue[tail]=i;
tail++;
book[i]=1;
}
//如果tail大于頂點(diǎn)個(gè)數(shù)，就跳出循環(huán)
if(tail>n) {
break;
}
}
head++;
}
//遍歷輸出隊(duì)列中的頂點(diǎn)
for(i=1;i<tail;i++) {
printf("%d ",queue[i]);
}
getchar();getchar();
return 0;
}
//輸出和輸出為
//5 5
//1 2
//1 3
//1 5
//2 4
//3 5
//1 2 3 5 4
城市地圖——圖的深度優(yōu)先遍歷
城市路徑求點(diǎn)到點(diǎn)的最短路徑.png
圖的鄰接矩陣.png
t1:圖的鄰接矩陣存儲的是路徑和路徑上的權(quán)值
t2:本題是求頂點(diǎn)1到頂點(diǎn)5的最短路徑
t3:示例代碼如下
#include <stdio.h>
//初始化
int min=99999999,book[101],n,e[101][101];
//遞歸函數(shù)(頂點(diǎn)試完之后要重置標(biāo)志位)
void dfs(int cur,int dis) {
if(dis>min) return;
if(cur==n) {
if(dis<min) min=dis;
return;
}
int j;
for(j=1;j<=n;j++) {
if(e[cur][j]!=99999999 && book[j]==0) {
book[j]=1;
dfs(j,dis+e[cur][j]);
book[j]=0;
}
}
return;
}
int main() {
int i,j,m,a,b,c;
scanf("%d %d",&n,&m);
//初始化鄰接矩陣
for(i=1;i<=m;i++) {
for(j=1;j<=n;j++) {
if(i==j) e[i][j]=0;
else e[i][j]=99999999;
}
}
//讀入邊
for(i=1;i<=m;i++) {
scanf("%d %d %d",&a,&b,&c);
e[a][b]=c;
}
book[1]=1;
dfs(1,0);
printf("一號城市到五號城市的最短路徑為%d",min);
getchar();getchar();
return 0;
}
//輸入和輸出為：
//5 8
//1 2 2
//1 5 10
//2 3 3
//2 5 7
//3 1 4
//3 4 4
//4 5 5
//5 3 3
//一號城市到五號城市的最短路徑為9
最少轉(zhuǎn)機(jī)——圖的廣度優(yōu)先遍歷
小哼和小哈.png
城市地圖.png
隊(duì)列過程.png
t1:本題是求頂點(diǎn)1到頂點(diǎn)5的最短路徑
t2:所有路徑的權(quán)值均為1
t3:示例代碼如下:
t4:5 7 1 5意思是五個(gè)頂點(diǎn)7條邊，起點(diǎn)為1，終點(diǎn)為5
#include <stdio.h>
//一個(gè)頂點(diǎn)
struct node {
int x; //城市編號
int s; //轉(zhuǎn)機(jī)次數(shù)
};
int main() {
//初始化
struct node que[2501];
int e[51][51]={0},book[51]={0};
int head,tail;
int i,j,n,m,a,b,cur,start,end,flag=0;
scanf("%d %d %d %d",&n,&m,&start,&end);
//初始化二維矩陣
for(i=1;i<=m;i++) {
for(j=1;j<=m;j++) {
if(i==j) e[i][j]=0;
else e[i][j]=99999999;
}
}
//讀入城市之間的航班
for(i=1;i<=m;i++) {
scanf("%d %d",&a,&b);
e[a][b]=1;
e[b][a]=1;
}
//隊(duì)列初始化
head=1;
tail=1;
que[tail].x=start;
que[tail].s=0;
tail++;
book[1]=start;
//只要隊(duì)列不為空
while(head<tail) {
//保存當(dāng)前頭結(jié)點(diǎn)
cur=que[head].x;
//嘗試頭結(jié)點(diǎn)連接的所有頂點(diǎn)
for(i=1;i<=n;i++) {
if(e[cur][i]!=99999999 && book[i]==0) {
que[tail].x=i;
que[tail].s=que[head].s+1;
book[i]=1;
tail++;
}
//到達(dá)目標(biāo)點(diǎn)
if(que[tail].x==end) {
flag=1;
break;
}
}
//如果找到則跳出while循環(huán)
if(flag==1)
break;
//沒到目標(biāo)點(diǎn)則繼續(xù)查找，head++;
head++;
}
printf("起點(diǎn)%d到終點(diǎn)%d的最短距離為%d",start,end,que[tail-1].s);
getchar();getchar();
return 0;
}
//輸入和輸出為：
//5 7 1 5
//1 2
//1 3
//2 3
//2 4
//3 4
//3 5
//4 5
//起點(diǎn)1到終點(diǎn)5的最短距離為2
