利用深度优先算法向算法进军

简介: 笔记

基于深度优先算法完成初级算法题


第一题:六角填数


如图所示六角形中,填入1~12的数字。

使得每条直线上的数字之和都相同。

3.png

具体操作在代码里面写得很清楚

#include<stdio.h>
int t[13];
int book[13];
void dfs(int step)
{
  int i;
  if (step == 13)    //判断是否12个数字都已经填入
  {
    if ((t[2] + t[3] + t[4] + t[5] )== (t[1] + t[3] + t[6] + t[8]) ==( t[1] + t[4] + t[7] + t[11]) == (t[8] + t[9] + t[10] + t[11]) == (t[2] + t[6] + t[9] + t[12]) == (t[5] + t[7] + t[10] + t[12]))
    {
      for (i = 1; i <= 12; i++)
        printf("%d ", t[i]);
      printf("\n");
    }
    return;
  }
  for (i = 1; i <=12; i++)
  {
    if (book[i] == 0)
    {
      book[i] = 1;   //标记这个数字已经填入了
      t[step] = i;    //填入该数字
      dfs(step + 1);   //进入下一个圈中
      book[i] = 0;   //取回填入的数字
    }
  }
  return;
}
int main(void)
{
  dfs(1);
  getchar(); getchar();
  return 0;
}

第二题:李白打酒

话说大诗人李白,一生好饮。幸好他从不开车。


一天,他提着酒壶,从家里出来,酒壶中有酒2斗。他边走边唱:


无事街上走,提壶去打酒。

逢店加一倍,遇花喝一斗。


这一路上,他一共遇到店5次,遇到花10次,已知最后一次遇到的是花,他正好把酒喝光了。


请你计算李白遇到店和花的次序,可以把遇店记为a,遇花记为b。则:babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢?请你计算出所有可能方案的个数(包含题目给出的)。

#include<stdio.h>
#include<stdlib.h>
char t[17], k[17];
int a = 0, b = 0;    //表示遇到店和花的次数
int total = 0,step =0;    //total表示答案的总数,step表示第多少次。
void dfs(int a,int b,int step)
{
  if (a == 9 && b == 5)   //判断遇到花和店的次数是否满足题意
  { 
    puts(t);
    total++;
    return;
  }
  if (a < 9)  //递归
  {
    t[step] = 'a';
    dfs(a + 1, b, step + 1);
    t[step] = '0';
  }
  if (b < 5)   //递归
  {
    t[step] = 'b';
    dfs(a, b + 1, step + 1);
    t[step] = '0';
  }
  return;
}
int main(void)
{
  dfs(a,b,0);
  system("pause");
  return 0;
}

第三题:地宫取宝

X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。


地宫的入口在左上角,出口在右下角。


小明被带到地宫的入口,国王要求他只能向右或向下行走。


走过某个格子时,如果那个格子中的宝贝价值比小明手中任意宝贝价值都大,小明就可以拿起它(当然,也可以不拿)。


当小明走到出口时,如果他手中的宝贝恰好是k件,则这些宝贝就可以送给小明。


请你帮小明算一算,在给定的局面下,他有多少种不同的行动方案能获得这k件宝贝。


【数据格式】


输入一行3个整数,用空格分开:n m k (1<=n,m<=50, 1<=k<=12)


接下来有 n 行数据,每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值


要求输出一个整数,表示正好取k个宝贝的行动方案数。该数字可能很大,输出它对 1000000007 取模的结果。


在我这里没有对它取模的操作。

例如,输入:

2 3 2

1 2 3

2 1 5

程序应该输出:

14

这里这个程序有点问题,它输出的是7,但大概的过程应该是这样的,欢迎各位大佬留言给点提示。

#include<stdio.h>
#include<stdlib.h>
int t[51][51], ;
int b[51], k, n, m,num=1;    //b计入拿起的每个宝藏的价值
int sum = 0;
void dfs(int x, int y)
{
  int next[2][2] = {
    {0,1},{1,0}
  };
  int i,tx,ty,j,flag=0;
  int a;
  if (x == n && y == m)
  {
    if (num == k)
    {
      sum++;
      printf("%d\n", sum);
    }
    return;
  }
  for (i = 0; i < 2; i++)
  {
    tx = x + next[i][0];   //向右走
    ty = y + next[i][1];  //向下走
    if (tx > n || ty > m)   //判断是否出界
      continue;
    for (j = 1; j <= num; j++)   //判断是否可以拿起宝藏
      if (t[tx][ty] <= b[j])
        flag = 1;
    if (flag == 0)    //如果可以
    {
      for (a = 0; a <= 1; a++)
      {
        if (a == 0)     //选择拿起该宝藏
        {
          num++;
          b[num] = t[tx][ty];
          dfs(tx, ty);
          b[num] = 0;
          num--;
        }
        else    //选择不拿起宝藏
        {                
          dfs(tx, ty);
        }
      }
    }
    else    //不可以拿起宝藏
    {
      dfs(tx, ty);
    }
  }
}
int main(void)
{
  int i,j;
  scanf_s("%d %d %d", &n, &m, &k);
  for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++)
      scanf_s("%d", &t[i][j]);
  b[1] = t[1][1];
  dfs(1, 1);
  system("pause");
}

thank for your reading!!!

公众号:FPGA之旅


目录
相关文章
|
6月前
|
监控 算法 机器人
软件体系结构 - 调度算法(2) 最低松弛度优先
【4月更文挑战第19天】软件体系结构 - 调度算法(2) 最低松弛度优先
172 0
|
6月前
|
存储 人工智能 算法
图与树的遍历:探索广度优先、深度优先及其他遍历算法的原理与实现
图与树的遍历:探索广度优先、深度优先及其他遍历算法的原理与实现
383 0
|
5月前
|
算法 Python
深度优先算法
深度优先算法
|
6月前
|
监控 算法 自动驾驶
软件体系结构 - 调度算法(1) 最早截至时间优先
【4月更文挑战第19天】软件体系结构 - 调度算法(1) 最早截至时间优先
313 0
|
2月前
|
算法 调度
作业调度算法_先来先服务算法_短作业优先算法_高响应比优先算法
本文介绍了作业调度算法,包括先来先服务(FCFS)、短进程优先(SJF)和高响应比优先(HRRN)算法。通过分析进程的到达时间和所需CPU服务时间,计算进程的开始时间、完成时间、平均周转时间和平均带权周转时间,以评估不同算法的性能。FCFS适合长作业,SJF适合短作业,而HRRN则综合了两者的优点。
79 12
|
4月前
|
算法 JavaScript
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)
66 0
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)
|
5月前
|
算法 Python
广度优先算法
广度优先算法
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
|
算法 Go C++
【LeetCode 算法专题突破】二叉树的深度优先遍历(⭐)
【LeetCode 算法专题突破】二叉树的深度优先遍历(⭐)
64 0