首页 > 编程语言 >C++编程-搜索与回溯算法2

C++编程-搜索与回溯算法2

时间:2024-09-07 22:51:36浏览次数:12  
标签:本书 10 题目 int 编程 C++ 算法 回溯 例题

目录

每日一诗

先言

正文

例题六

题目描述

算法分析

标准程序

例题七:选书

题目描述

算法分析

标准程序

输出

例题八:跳马问题

题目描述

标准程序

小练习

题目描述

输入

输出

样例输入 复制

样例输出 复制


每日一诗

红豆生南国,春来发几枝。

愿君多采撷,此物最相思。

Red beans grow in the south.In spring, how many branches sprout?
I hope you pick many.This thing evokes the most yearning.

先言

今天讲解搜索与回溯算法的第二期,会着重讲解剩下的部分例题,还会留下小练习作为作业

正文

例题六

题目描述

设有A,B,C,D,E五人从事J1,J2,J3,J4,J5五项工作,每人只能从事一项,他们的效益如下。

每人选择五项工作中的一项,在各种选择的组合中,找到效益最高的的一种组合输出。

算法分析

    ⒈用数组f储存工作选择的方案;数组g存放最优的工作选择方案;数组p用于表示某项工作有没有被选择了。

    ⒉(1)选择p(i)=0的第i项工作;

       (2)判断效益是否高于max已记录的效益,若高于则更新g数组及max的值。

    ⒊搜索策略: 回溯法(深度优先搜索dfs)。

标准程序

#include<bits/stdc++.h>
using namespace std;
int  data[6][6]={{0,0,0,0,0,0},{0,13,11,10,4,7},{0,13,10,10,8,5},{0,5,9,7,7,4},
                          {0,15,12,10,11,5},{0,10,11,8,8,4}};
int max1=0,g[10],f[10];
bool p[6]={0};
int go(int step,int t)                   // step是第几个人,t是之前已得的效益
{  
    for (int i=1;i<=5;i++)
    if (!p[i])                                    //判断第i项工作没人选择
     { 
          f[step]=i;                           //第step个人,就选第i项工作
          p[i]=1;                                //标记第i项工作被人安排了
          t+=data[step][i];               //计算效益值
          if (step<5) go(step+1,t);
          else if (t>max1)                //保存最佳效益值
          {
               max1=t;
               for (int j=1;j<=5;j++)
                   g[j]=f[j];                   //保存最优效益下的工作选择方案
           }
          t-=data[step][i];               //回溯
          p[i]=0;
     }
}
int main()
{
     go(1,0);                                             //从第1个人,总效益为0开始
     for (int i=1;i<=5;i++)
        cout<<char(64+i)<<":J"<<g[i]<<setw(3); //输出各项工作安排情况
     cout<<endl;
     cout<<"supply:"<<max1<<endl;   //输出最佳效益值
}

例题七:选书

题目描述

       学校放寒假时,信息学竞赛辅导老师有A,B,C,D,E五本书,要分给参加培训的张、王、刘、孙、李五位同学,每人只能选一本书。老师事先让每个人将自己喜欢的书填写在如下的表格中。然后根据他们填写的表来分配书本,希望设计一个程序帮助老师求出所有可能的分配方案,使每个学生都满意。

算法分析

       可用穷举法,先不考虑“每人都满意” 这一条件,这样只剩“每人选一本且只能选一本”这一条件。在这个条件下,可行解就是五本书的所有全排列,一共有5!=120种。然后在120种可行解中一一删去不符合“每人都满意”的解,留下的就是本题的解答。

       为了编程方便,设1,2,3,4,5分别表示这五本书。这五个数的一种全排列就是五本书的一种分法。例如54321就表示第5本书(即E)分给张,第4本书(即D)分给王,……,第1本书(即A)分给李。“喜爱书表”可以用二维数组来表示,1表示喜爱,0表示不喜爱。

算法设计:S1:产生5个数字的一个全排列;

                  S2:检查是否符合“喜爱书表”的条件,如果符合就打印出来;

                  S3:检查是否所有的排列都产生了,如果没有产生完,则返回S1;

                  S4:结束。

       上述算法有可以改进的地方。比如产生了一个全排列12345,从表中可以看出,选第一本书即给张同学的书,1是不可能的,因为张只喜欢第3、4本书。这就是说,1××××一类的分法都不符合条件。由此想到,如果选定第一本书后,就立即检查一下是否符合条件,发现1是不符合的,后面的四个数字就不必选了,这样就减少了运算量。换句话说,第一个数字只在3、4中选择,这样就可以减少3/5的运算量。同理,选定了第一个数字后,也不应该把其他4个数字一次选定,而是选择了第二个数字后,就立即检查是否符合条件。例如,第一个数选3,第二个数选4后,立即检查,发现不符合条件,就应另选第二个数。这样就把34×××一类的分法在产生前就删去了。又减少了一部分运算量。

       综上所述,改进后的算法应该是:在产生排列时,每增加一个数,就检查该数是否符合条件,不符合,就立刻换一个,符合条件后,再产生下一个数。因为从第I本书到第I+1本书的寻找过程是相同的,所以可以用回溯算法。算法设计如下(不是标准程序,只是思路):

int Search(i)
{
     for (j=1;j<=5;j++)
     {
          if (第i个同学分给第j本书符合条件)
          {
               记录第i个数
               if (i==5) 打印一个解;
                     else Search(i+1);
               删去第i 个数
          }
     }
}

标准程序

#include<bits/stdc++.h>
using namespace std;
int  book[6],c;
bool flag[6],like[6][6]={{0,0,0,0,0,0},{0,0,0,1,1,0},{0,1,1,0,0,1},
                                       {0,0,1,1,0,0},{0,0,0,0,1,0},{0,0,1,0,0,1}};;
int  search(int);
int  print();
int  main()
{
    for (int i=1;i<=5;i++)  flag[i]=1;  
    search(1);                                    //从第1个开始选书,递归。
} 
int search(int i)                                //递归函数 
{
    for (int j=1;j<=5; j++)                 //每个人都有5本书可选
    if (flag[j]&&like[i][j])                 //满足分书的条件
    {
        flag[j]=0;                                 //把被选中的书放入集合flag中,避免重复被选
        book[i]=j;                                //保存第i个人选中的第j本书
        if (i==5) print();                      //i=5时,所有的人都分到书,输出结果 
            else search(i+1);                  //i<5时,继续递归分书
        flag[j]=1;                                 //回溯:把选中的书放回,产生其他分书的方案
        book[i]=0;
  }
}  
int print()
{
    c++;                                        //方案数累加1
    cout <<"answer " <<c <<":\n";  
    for (int i=1;i<=5;i++)
      cout <<i <<": " <<char(64+book[i]) <<endl;  //输出分书的方案
}

输出

answer 1

1: C

2: A

3: B

4: D

5: E

例题八:跳马问题

题目描述

在5*5格的棋盘上,有一只中国象棋的马,从(1,1)点出发,按日字跳马,它可以朝8个方向跳,但不允许出界或跳到已跳过的格子上,要求在跳遍整个棋盘。

输出前5个方案及总方案数。

输出格式示例:

  1  16   21   10   25

20  11   24   15   22

17    2   19     6     9

12    7     4   23   14

  3  18   13     8     5

标准程序

#include<bits/stdc++.h>
using namespace std;
int u[8]={1,2,2,1,-1,-2,-2,-1},    //8个方向上的x,y增量
     v[8]={-2,-1,1,2,2,1,-1,-2};
int a[100][100]={0},num=0;      //记每一步走在棋盘的哪一格和棋盘的每一格有没有被走过
bool b[100][100]={0};
int search(int,int,int);                  //以每一格为阶段,在每一阶段中试遍8个方向
int print();                                   //打印方案
int search(int i,int j,int n)
{
     int k,x,y;                                        //这三个变量一定要定义局部变量
     if (n>25) { print(); return 0; }       //达到最大规模打印、统计方案
     for (k=0;k<=7;k++)                       //试遍8个方向
    {
          x=i+u[k];y=j+v[k];                  //走此方向,得到的新坐标
          if (x<=5&&x>=1&&y<=5&&y>=1&&(!b[x][y]))
          {                                            //如果新坐标在棋盘上,并且这一格可以走
               b[x][y]=1; 
               a[x][y]=n;
               search(x,y,n+1);                 //从(x,y)去搜下一步该如何走
               b[x][y]=0;
               a[x][y]=0; 
          }
     }
}
int print()
{
     num++;                                    //统计总方案
     if (num<=5)                             //打印出前5种方案
     {
          for (int k=1;k<=5;k++)       //打印本次方案
          {
                for (int kk=1;kk<=5;kk++)
                     cout<<setw(5)<<a[k][kk];
                cout<<endl;  
          }
     }
}

小练习

因为OJ题库出了点问题,导致无法放置太多题目,这里给大家一个最简单的题目

点我提交

题目描述

斐波那契数列0,1,1,2,3,5,8,13,21,34,55……从第三项起,每一项都是紧挨着的前两项的和。写出计算斐波那契数列任意一个数据项的递归程序。

输入

所求项数

输出

数据项的值

样例输入 复制
10
样例输出 复制
34

标签:本书,10,题目,int,编程,C++,算法,回溯,例题
From: https://blog.csdn.net/weixin_68261272/article/details/141969199

相关文章

  • Java 入门指南:Java 并发编程 —— 并发容器 ConcurrentLinkedDeque
    文章目录ConcurrentLinkedDeque特点构造方法常用方法使用示例注意事项ConcurrentLinkedDequeConcurrentLinkedDeque是Java并发工具包(java.util.concurrent包)中的一个线程安全的双端队列(Deque)实现,实现了Deque接口。它使用了链表结构,并且针对高并发环境进行了......
  • 条款05: 了解c++默默编写并调用哪些函数
    1.如果没有声明任何构造函数,编译器会为你声明一个default构造函数2.惟有default构造函数被需要,才会被编译器创建出来classEmpty{public:Empty(){}//1.默认构造~Empty(){}//2.析构函数Empty(constEmpty&rhs){}//3.copy构造Empty&operator=(c......
  • 《深入探究 <侠盗猎车手 5>(GTA5)的 C++ 代码世界》
    在游戏的浩瀚宇宙中,《侠盗猎车手5》(GrandTheftAutoV,简称GTA5)无疑是一颗璀璨的巨星。这款游戏以其庞大的开放世界、精彩的剧情和令人惊叹的游戏玩法,吸引了全球无数玩家。而在其背后,C++代码起着至关重要的作用。一、游戏引擎的C++魔法GTA5采用了Rockstar自研的强......
  • 网络编程
    网络编程可以让设备中的程序与网络上的其他设备中的程序进行数据交互,实现网络通信。基本的通信架构基本通信架构有两种:CS架构(Client客户端/Server服务端)、BS架构(Browser浏览器/Server服务端)。网络通信三要素InetAddress(IP地址)publicclasstest{publicstaticvoidmain(Stri......
  • Python面向对象编程:学生类的实现与应用
    在现代编程中,面向对象编程(Object-OrientedProgramming,OOP)是一种非常重要的编程范式。它通过类和对象的概念,将现实世界的实体抽象成程序中的对象,从而实现对复杂系统的建模。本文将通过一个简单的学生类的例子,带大家了解如何使用Python实现面向对象编程。一、代码简介下面......
  • 面向对象编程的学习路线
    一、基础概念面向对象编程的基本概念面向对象编程是一种编程范式,它将数据和操作数据的方法封装在对象中。通过使用类和对象,我们可以更好地组织和管理代码。在面向对象编程中,我们可以使用继承、多态和封装等特性来提高代码的可重用性、可扩展性和可维护性。学习面向对象编程的基本概......
  • 东方博宜oj题解1161-1165(c++)
    各位读者们,抱歉,因为最近的时间原因,所以更新频率比较低。1161:1161-元素插入有序数组-东方博宜OJ#include<bits/stdc++.h>usingnamespacestd;intmain(){ intn,s,c; cin>>c>>n; inta[n];//定义数组 for(inti=0;i<n;i++){ cin>>a[i]; } s=n;//设c是最大的......
  • C++小游戏集3个(不定时更新)2
    前言在Dvec++中想做游戏是很难的,但我不这么想,在下写了一些小游戏给客官看看废话不多说,上代码!!!一、表白神器表白很好用(真的)#include<stdio.h>#include<math.h>#include<windows.h>#include<stdio.h>#include<math.h>#include<stdlib.h>#include<string.h>int......
  • [c++][笔记]浅谈几种排序方式---冒泡排序,选择排序,桶排序
     一、algorithm里的sort函数 #include<cstdio>//数据小的可以用iostream#include<algorithm>//不能忘记算法库,否则会编译失败。usingnamespacestd;intmain(){intn;scanf("%d",&n);inta[n+5]={};for(inti=1;i<=n;i++){......
  • C++ 模板基础知识——可变参数模板
    目录C++模板基础知识——可变参数模板1.可变参函数模板1.1基本含义1.2利用constexprif优化递归函数1.3关于constexprif的进一步理解1.4重载2.折叠表达式2.1一元左折(UnaryLeftFold)2.2一元右折(UnaryRightFold)2.3二元左折(BinaryLeftFold)2.4二元右折......