Intro
啊哈淹冰，算法封面.png
t1.這篇文章記錄我的一個學(xué)習(xí)和心得
t2.需要c語言基礎(chǔ)
t3.需要數(shù)據(jù)結(jié)構(gòu)和算法的基礎(chǔ)
t4.Just Do it!
一大波樹數(shù)正在靠近——排序
本節(jié)講的是簡化版桶排序法，事件復(fù)雜度為O(M+N)巨柒，這是一種非秤Ｋ快的排序算法柠衍，從1956年開始被使用。但它的缺點是非常的浪費空間晶乔。
對數(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個數(shù)
for(i=1;i<=5;i++) {
scanf("%d",&t);
a[t]++;
}
//遍歷每一個桶珍坊，并輸出每一個桶內(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("請輸入讀入元素的個數(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是桶的個數(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ù)
鄰居好說話——冒泡排序
冒泡排序的基本思想是：每次比較倆個相鄰的數(shù)字，如果他們順序錯誤翻具，則進(jìn)行交換位置冒泡排序的時間度是O(N方)履怯，這是一個非常高的時間復(fù)雜度。
冒泡排序.png
#include <stdio.h>
int main() {
int a[100],i,j,t,n;
printf("請輸入你要排序的個數(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++) { //每一躺比較的元素個數(shù)n-i
if(a[j]>a[j+1]) {
t = a[j]; //臨時存儲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("請輸入你要比較的元素的個數(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;
}
最常用的排序——快速排序
冒泡排序雖然解決了桶排序的極大浪費空間的問題叹洲，但是它的算法執(zhí)行效率上卻犧牲了很多，它的時間復(fù)雜度為O(N方)工禾，假如我們的計算機是運算次數(shù)是10億/s运提，那么對1億個數(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ù)元素的個數(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;
}
//快速排序是由英國計算機科學(xué)家 Tony Hoare 發(fā)明，是一位偉大的英國計算機科學(xué)家
//快速排序是分治法的一種思想
//哨兵i,j
//首先竟痰，找一個基準(zhǔn)數(shù)签钩，一般我們把第一個數(shù)作為基準(zhǔn)數(shù)
//然后，從右邊找一個小于基準(zhǔn)數(shù)的值并記錄索引的位置坏快，這個過程是j--
//然后同理從左邊找一個大于基準(zhǔn)數(shù)的值并記錄索引铅檩，這個過程是i++
//都找到后交換位置
//當(dāng)i=j，交換位置莽鸿，更新基準(zhǔn)數(shù)
//快速排序最差的情況的它的執(zhí)行效率和冒泡排序一樣都是O(N方),平均時間復(fù)雜度是O(NlogN)
小哼買書——練習(xí)測試
q1:輸入一串1~1000的整數(shù)昧旨，去重且排序，完成后輸出數(shù)據(jù)元素的個數(shù)祥得。
最終效果.png
思路一：使用改變的桶排序法可以實現(xiàn)
思路二：使用冒泡先排序兔沃，后去重，就是從第二個開始级及，比較與前一個數(shù)是否相等乒疏，不相等則輸出
思路三：快速排序，最優(yōu)解法饮焦！
總結(jié)：綜上所述怕吴，我們的ISBN是在1-1000窍侧，范圍太小，如果是-2億~2億呢转绷？或者n接近10萬呢伟件？冒泡排序則需要數(shù)十秒，快速排序則只需要 0.0017s,差距是多么的大议经，這就是算法的魅力!
//這里只給出桶排序的實現(xiàn)方法
#include <stdio.h>
int main() {
//j是去重后的元素的個數(shù)
int a[1000],i,j,t,n;
//初始化數(shù)組
for(i=1;i<1001;i++) {
a[i] = 0;
}
//輸入
printf("請輸入ISBN的總個數(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ù)組的索引
棧煞肾，隊列其骄，鏈表
解密QQ號——隊列
規(guī)則是這樣的：首先將第 1 個數(shù)刪除，緊接著將第 2 個數(shù)放到這串?dāng)?shù)的末尾扯旷，再將第 3 個數(shù)刪除并將第 4 個數(shù)放到這串?dāng)?shù)的末尾拯爽，再將第 5 個數(shù)刪除……直到剩下后一個數(shù)，將最后一個數(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]); //輸出第一個數(shù)
head++; //頭游標(biāo)自增
a[tail]=a[head]; //將第二個數(shù)移到后邊
tail++; //尾游表自增
head++; //重新一輪
}
getchar();getchar();
return 0;
}
//這個小算法相當(dāng)于幫助我們了解隊列的概念
//使用結(jié)構(gòu)體實現(xiàn)解密QQ號的算法
#include <stdio.h>
//隊列
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) { //隊列不為空時
//刪除數(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;
//讀入字符串的個數(shù)
scanf("%d",&n);
//讀入n個字符并存儲
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ī)則是這樣的：將一副撲克牌平均分成兩份耸黑，每人拿一份桃煎。小哼先拿出手的
第一張撲克牌放在桌上，然后小哈也拿出手中的第一張撲克牌大刊，并放在小哼剛打出牌
的上面为迈，就像這樣兩人交替出牌。出牌時缺菌，如果某人打出的牌與桌上某張牌的牌面相同葫辐，即可將兩張相同的牌及其中間所夾的牌全部取走，并依次放到自己手中牌尾伴郁。任意一人手中的牌全部出完時耿战，游戲結(jié)束，對手獲勝焊傅。
結(jié)果的驗證.png
#include <stdio.h>
//模擬我們手牌的隊列
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é)點.png
關(guān)于使用c實現(xiàn)鏈表需要注意的幾點:
t1:怎么分配結(jié)點的內(nèi)存空間剂陡，我們使用 (type 星號)malloc(sizeof(dataType)) 來動態(tài)聲明內(nèi)存空間。
t2:因為我們的節(jié)點是指針狐胎，訪問每一個節(jié)點的內(nèi)部成員要使用指針運算符'->'符號鸭栖，如p->data=1。
t3:具體實現(xiàn)代碼會在下面的代碼塊給出握巢。
/*----使用c的結(jié)構(gòu)體+動態(tài)內(nèi)存分配malloc函數(shù)實現(xiàn)單鏈表----*/
#include <stdio.h>
#include <stdlib.h>
//表示一個節(jié)點
struct node {
int data;
struct node *next;
};
int main() {
//初始化（頭結(jié)點head,臨時結(jié)點q,迭代結(jié)點q,遍歷臨時頭結(jié)點t）
struct node *head,*p,*q,*t;
int i,n,a;
//要讀取幾個數(shù)
scanf("%d",&n);
//循環(huán)讀入n個數(shù)
for(i=1;i<=n;i++) {
scanf("%d",&a);
//動態(tài)申請一個內(nèi)存空間晕鹊，初始化結(jié)點
p = (struct node *)malloc(sizeof(struct node));
p->data=a;
p->next=NULL;
//判斷頭結(jié)點是否為空
if(head==NULL) {
head=p;
}else{
q->next=p;
}
//更新迭代結(jié)點
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é)，實現(xiàn)單鏈表的插入結(jié)點的操作----------*/
#include <stdio.h>
#include <stdlib.h>
//結(jié)點結(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é)點
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é)點
p->next=t->next;
t->next=p;
break;
}
t=t->next;
}
//遍歷結(jié)點
t=head;
while(t != NULL) {
printf("%d ",t->data);
t=t->next;
}
//暫停程序
getchar();getchar();
//退出程序
return 0;
}
//需要注意的是遍歷所有節(jié)點的下一個節(jié)點的操作那里，要使用while循環(huán)包上if條件判斷
//置換節(jié)點那里理清思路即可
//測試打印的日志為
//5
//1 3 5 7 9
//6
//1 3 5 6 7 9
模擬鏈表
模擬鏈表的實現(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:實現(xiàn)的代碼在下邊
#include <stdio.h>
int main() {
int data[101],right[101];
int i,n,t,len;
//讀入n個數(shù)
scanf("%d",&n);
len=n;
//循環(huán)讀入n個數(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ù)組末尾增加一個數(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ù)的索引
//使用模擬鏈表可以實現(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:因為 456 + 123 = 579 和t1重復(fù)了，所以我們需要將計算的結(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;
}
//如果某個數(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:給出一個二維的數(shù)組模擬我們的整個地圖
t2:使用 "#" 表示墻程腹， "." 表示空地， "G" 表示敵人
t3:如是是向上遍歷地圖儒拂，則是y不變x--,可以結(jié)合上圖看
t4:請寫出相關(guān)的算法寸潦，算出將炸彈放在哪個位置炸死的敵人最多
#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個以內(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)前遍歷的格子存儲在臨時變量x和y中
x=i;y=j;
//向上統(tǒng)計可以消滅敵人的數(shù)量
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
x--;
}
//向下統(tǒng)計可以消滅敵人的數(shù)量
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
x++;
}
//向左統(tǒng)計可以消滅敵人的數(shù)量
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
y--;
}
//向右統(tǒng)計可以消滅敵人的數(shù)量
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
y++;
}
if(sum>map) {
//更新和記錄能消滅敵人的最大數(shù)量
map=sum;
//同時更新坐標(biāo)(哪行哪列)
p=i;
q=j;
}
}
}
}
printf("將炸彈放置在%d行%d列社痛，最多可以消滅%d個敵人",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個敵人
火柴棍等式
每個數(shù)字需要用到的火柴棍的個數(shù).png
t1:加號和等于號各需要2根火柴棍
t2:如果a不等于b，a+b=c 和 b+a=c 視為不同的等式(a,b,c都大于0)
t3:所有火柴棍必須都用上蒜哀，假設(shè)有火柴棍24個斩箫，即24-4=20個
t4:假如某人有m根火柴，那么究竟可以拼出多少個a+b=c的等式
t5:設(shè)計求解算法撵儿，要求時間復(fù)雜度為O(N方)
#include <stdio.h>
//得到一個數(shù)字的火柴的個數(shù)
int fun(int x) {
//記錄已經(jīng)使用的火柴的數(shù)量
int num=0;
//記錄0~9數(shù)字的火柴棍的個數(shù)
int f[10] = {6,2,5,5,4,5,6,3,7,6};
//如果x不是一位數(shù)
while(x/10!=0) {
//獲得末尾的數(shù)字的火柴的個數(shù)
num+=f[x%10];
//取出末尾的數(shù)字
x/=10;
}
//出了上面的while循環(huán),x必定是一位數(shù)
num+=f[x];
//返回火柴的總個數(shù)
return num;
}
int main() {
//初始化變量
int a,b,c,m,i,sum=0; //sum是用來計數(shù)的乘客，因此一定要初始化為0
//讀入火柴棍的個數(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個不同的等式",sum);
//暫停程序
getchar();getchar;
//結(jié)束程序
return 0;
}
//要枚舉a b c,就要想到三個數(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個不同的等式
數(shù)的全排列
數(shù)字123的全排列.png
t1:請設(shè)計一個算法淀歇，實現(xiàn)1234的數(shù)字的全排列
t2:我們可以使用四層for循環(huán)嵌套篩選和過濾出滿足 a!=b a!=c a!=d b!=c b!=d c!=d的排列
t3:具體實現(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:接上邊的那個算法
t2:輸入3,就是求123的全排列寨典，4就是1234的全排列，(0<n<9)
#include <stdio.h>
int a[10],book[10],n;
void dfs(int step) { //step表示我們當(dāng)前在第幾個盒子面前
int i;
if(step==n+1) {
for(i=1;i<=n;i++) {
printf("%d",a[i]);
}
printf("\n");
return;
}
//此時站在第step個盒子面前房匆，要考慮放哪張牌的問題
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;
//封裝到每一個箱子面前要進(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() {
//表示有幾個箱子耸成，其實就是數(shù)字一共有9為，如123+456=579
n=9;
//從第一個箱子開始
dfs(1);
//暫停程序
getchar();getchar();
//退出程序
return 0;
}
解救小哈
要走的四個方向的關(guān)系變化圖.png
t1:使用深度優(yōu)先搜索找到最段路徑
t2:遍歷查找的方向依次為右下左上(順時針)查找浴鸿，這里我們使用了一個int[4][2]的二維數(shù)組
t3:具體的實現(xiàn)的代碼如下
/*使用深度優(yōu)先的算法求倆點的最短路徑*/
#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) {
//定義一個二維的數(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++) {
//計算下一個方向
tx=x+next[k][0];
ty=y+next[k][1];
//如果越界井氢，就直接進(jìn)行計算下一個方向
if(tx<1 || tx>n || ty<1 || ty>m)
continue;
//判斷該店是否為障礙物且已經(jīng)在路徑中
if(a[tx][ty]==0 && book[tx][ty]==0) {
//標(biāo)記這個點為已經(jīng)走過
book[tx][ty]=1;
//嘗試下一個點
dfs(tx,ty,step+1);
//嘗試結(jié)束，取消這個點的標(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]);
}
}
//讀入起點和終點
scanf("%d %d %d %d",&startx,&starty,&p,&q);
//從起點開始走
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:實現(xiàn)的代碼如下
#include <stdio.h>
//結(jié)點結(jié)構(gòu)體
struct note {
int x; //橫坐標(biāo)
int y; //縱坐標(biāo)
int f; //父親在隊列中的編號
int s; //步數(shù)
};
int main() {
struct note queue[2501]; //隊列
//存儲地圖的二位數(shù)組和book標(biāo)記數(shù)組
int a[51][51] = {0};
int book[51][51] = {0};
//定義一個方向的數(shù)組，依次是右下左上
int next[4][2] = {{0,1},
{1,0},
{0,-1},
{-1,0}};
//隊列的頭尾標(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]);
//輸入起點和終點
scanf("%d %d %d %d",&startx,&starty,&p,&q);
//隊列的初始化
head=1;
tail=1;
//往隊列插入起點
queue[tail].x = startx;
queue[tail].y = starty;
queue[tail].f = 0;
queue[tail].s = 0;
tail++;
//標(biāo)記起點為已走過
book[startx][starty] = 1;
//flag為0未找到終點，1則是找到
flag = 0;
//當(dāng)隊列不為空
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;
//如果這個點為0即空地且未被標(biāo)記
if(a[tx][ty]==0 && book[tx][ty]==0) {
//滿足條件约急，加入到隊列中
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á)終點
if(tx==p && ty==q) {
flag=1;
break;
}
}
if(flag==1)
break;
head++;
}
//輸出到目標(biāo)點一共走了多少步
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ù)字的賦值我們這里可以使用下面的方式零远，給一個for循環(huán)，里面加上scanf("%s",a[i]);這樣
t4:上面表示接受了多少行字符厌蔽，不用加取地址符&
t5:具體代碼如下
#include <stdio.h>
//表示一個位置結(jié)點
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;
//四個方向
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++) {
//求出下一個要搜索的位置結(jié)點
tx=queue[head].x+next[k][0];
ty=queue[head].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;
queue[tail].x=tx;
queue[tail].y=ty;
tail++;
sum=getnum(tx,ty);
if(sum>max) {
//更新最小值min和記錄結(jié)點的位置
max=sum;
mx=tx;
my=ty;
}
}
}
head++;
}
printf("將炸彈人放在(%d,%d)個位置上牵辣，最多可以消滅%d個敵人",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)個位置上，最多可以消滅10個敵人
使用深搜再解炸彈人
t1:思路就是使用深度優(yōu)先遍歷的方法奴饮，遍歷每一個點纬向，最后會記錄的一個點的位置，這個位置炸死的敵人的數(shù)量是最多的
t2:只需要把dfs的每一步做好就行戴卜，在每一個點進(jìn)行遍歷逾条，計算炸死的敵人的數(shù)量即可
t3:實現(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) {
//定義一個用戶表示方向的數(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++) {
//計算下一個要遍歷的點
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)個位置，最多可以消滅%d個敵人",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)個位置投剥，最多可以消滅10個敵人
寶島探險
使用廣搜解決島嶼的面積的問題
寶島探險.png
t1:有一個10*10大小的二維矩陣是一個寶島的航拍地圖师脂，使用數(shù)字0代表海洋，使用數(shù)字1~9代表陸地
t2:現(xiàn)在假設(shè)小哼要降落在某個島上并算出這個島的面積
t3:我們可以使用廣度優(yōu)先搜索方法解決這個問題
t4:頂一個一個變量江锨，遍歷每一個格子危彩，如果是大于1， 變量就進(jìn)行自增
t5:最后輸出這個變量就是這個島嶼的面積
#include <stdio.h>
//0海洋 1~9表示陸地
//格子不超過50*50
//表示一個結(jié)點
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;
//把小哼降落的位置加入到隊列
queue[head].x=startx;
queue[head].y=starty;
tail++;
book[startx][starty]=1;
sum=1;
//要遍歷的四個方向
int next[4][2]={{0,1},
{1,0},
{0,-1},
{-1,0}};
//隊列不為空
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++) {
//計算下一個點
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é)
寶島探險添加參數(shù)color
t1:只是給遞歸函數(shù)dfs添加了一個新的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;
//四個方向
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);
}
}
//這個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
寶島探險求得海洋上小島的個數(shù)
t1:思路還是使用深度優(yōu)先搜索
t2:改變的只是添加了一個num參數(shù)，每次找到一個小島的一部分，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;
//將這個格子進(jìn)行染色
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) {
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]);
}
}
//遞歸計算一共有幾個小島
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個小島",-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個小島
水管工游戲
水管工游戲.png水管連通之后.png每個數(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)記這個管道已經(jīng)遍歷過
book[x][y]=1;
//當(dāng)前水管是直管的時候
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í)行下面這個操作返回到上一次的地方
//這里是個難點，也是區(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è)方案
水管工游戲保存和輸出路徑點
t1:就是添加了一個結(jié)構(gòu)體和結(jié)構(gòu)體的數(shù)組
t2:添加了一個新的標(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)記這個管道已經(jīng)遍歷過
book[x][y]=1;
top++;
s[top].x=x;
s[top].y=y;
//當(dāng)前水管是直管的時候
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
圖的頂點的訪問順序.png
t1:本題要求使用深度優(yōu)先搜索遍歷所有頂點并輸出頂點
t2:圖三是使用深度優(yōu)先搜索遍歷輸出頂點的順序壳鹤，頂點旁邊的數(shù)字我們叫做事件戳
t3:實現(xiàn)代碼如下
#include <stdio.h>
//初始化變量
int book[101],e[101][101],sum=0,n,inf=99999999;
//深度優(yōu)先搜索
void dfs(int cur) {
//初始化變量并輸出當(dāng)前遍歷的點
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是頂點的個數(shù)，m的邊的個數(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;
}
//從一號頂點開始深度優(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:遍歷方式改為廣搜芳誓，實現(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是頂點個數(shù)，m是邊的個數(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;
}
//初始化隊列的頭尾節(jié)點
head=1;
tail=1;
//將第一個頂點添加到隊列中
queue[tail]=1;
tail++;
book[1]=1;
//當(dāng)隊列不為空
while(head<tail) {
//當(dāng)前藥遍歷的根節(jié)點
cur=queue[head];
//遍歷所有節(jié)點
for(i=1;i<=n;i++) {
if(e[cur][i]==1 && book[i]==0) {
queue[tail]=i;
tail++;
book[i]=1;
}
//如果tail大于頂點個數(shù)啊鸭，就跳出循環(huán)
if(tail>n) {
break;
}
}
head++;
}
//遍歷輸出隊列中的頂點
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)先遍歷
城市路徑求點到點的最短路徑.png
圖的鄰接矩陣.png
t1:圖的鄰接矩陣存儲的是路徑和路徑上的權(quán)值
t2:本題是求頂點1到頂點5的最短路徑
t3:示例代碼如下
#include <stdio.h>
//初始化
int min=99999999,book[101],n,e[101][101];
//遞歸函數(shù)(頂點試完之后要重置標(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)機——圖的廣度優(yōu)先遍歷
小哼和小哈.png
城市地圖.png
隊列過程.png
t1:本題是求頂點1到頂點5的最短路徑
t2:所有路徑的權(quán)值均為1
t3:示例代碼如下:
t4:5 7 1 5意思是五個頂點7條邊锹淌，起點為1，終點為5
#include <stdio.h>
//一個頂點
struct node {
int x; //城市編號
int s; //轉(zhuǎn)機次數(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;
}
//隊列初始化
head=1;
tail=1;
que[tail].x=start;
que[tail].s=0;
tail++;
book[1]=start;
//只要隊列不為空
while(head<tail) {
//保存當(dāng)前頭結(jié)點
cur=que[head].x;
//嘗試頭結(jié)點連接的所有頂點
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)點
if(que[tail].x==end) {
flag=1;
break;
}
}
//如果找到則跳出while循環(huán)
if(flag==1)
break;
//沒到目標(biāo)點則繼續(xù)查找赠制，head++;
head++;
}
printf("起點%d到終點%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
//起點1到終點5的最短距離為2
