第一讲之递归与递推下篇

第一讲之递归与递推下篇

  • 带分数
  • 费解的开关
  • 飞行员兄弟
  • 翻硬币

带分数

在这里插入图片描述

用暴力将所有全排列的情况都算出来
在这里插入图片描述> 有三个数，a,b,c
每种排列情况，可以用两层for循环，暴力分为三个部分，每个部分一个数
在这里插入图片描述

当然注意这里，第一层for循环，小于7.因为一共9个数，要保证剩下2个数不为0，要留2个位置
第二层循环，小于8，要保证剩下一个数不为0了，要留一个位置

如果边界值都写小于9的话，那么就会出现a,b,c三个数出现0的情况，这个时候，我们就要特殊的判断下

#include <iostream>

using namespace std;

const int N = 10;

int target;  // 题目给出的目标数
int num[N];  // 保存全排列的结果
bool used[N];  // 生成全排列过程中标记是否使用过
int cnt;  // 计数，最后输出的结果

// 计算num数组中一段的数是多少
int calc(int l, int r) {
  int res = 0;
  for (int i = l; i <= r; i++) {
    res = res * 10 + num[i];
  }
  return res;
}

// 生成全排列
// 当全排列生成后进行分段
void dfs(int u) {
  // 用两层循环分成三段
  if (u == 9) {
    for (int i = 0; i < 7; i++) {
      for (int j = i + 1; j < 8; j++) {
        int a = calc(0, i);
        int b = calc(i + 1, j);
        int c = calc(j + 1, 8);
        // 注意判断条件，因为C++中除法是整除，所以要转化为加减乘来计算
        if (a * c + b == c * target) {
          cnt++;
        }
      }
    }
    return;
  }
  // 搜索模板
  for (int i = 1; i <= 9; i++) {
    if (!used[i]) {
      used[i] = true; // 标记使用
      num[u] = i;
      dfs(u + 1);
      used[i] = false; // 还原现场
    }
  }
}

int main() {
  scanf("%d", &target);
  dfs(0);
  printf("%d\n", cnt);
  return 0;
}

C++STL函数中也有现成的全排列函数(next_permutation等)，可以不用自己手写

#include <bits/stdc++.h>

using namespace std;

const int N = 10;

int target;
int num[N];

int calc(int l, int r) {
  int res = 0;
  for (int i = l; i <= r; i++) {
    res = res * 10 + num[i];
  }
  return res;
}

int main() {
  cin >> target;
  for (int i = 0; i < 9; i++) {
    num[i] = i + 1;
  }
  int res = 0;
  do {
    for (int i = 0; i < 9; i++) {
      for (int j = i + 1; j < 9; j++) {
        int a = calc(0, i);
        int b = calc(i + 1, j);
        int c = calc(j + 1, 8);
        if (a == 0 || b == 0 || c == 0) {
          continue;
        }
        if (a * c + b == c * target) {
          ++res;
        }
      }
    }
    // 调用函数生成全排列
  } while (next_permutation(num, num + 9));
  cout << res << '\n';
  return 0;
}

这主要用两层dfs嵌套来做
先dfs算出a,每个dfs算出的a中，在dfs c,b的话可以根据a与c的值来算

#include<iostream>
#include<cstdio>
#include<cstring>


using namespace std;

const int N = 10;

int n;    //目标数
bool used[N], backup[N];  //全排列的状态数组
int num[N];   //存储全排列的数据
int ans;


bool check(int a, int c)
{
     long long b = n * (long long)c - a * c;
     
     
     if(!a || !b || !c) {return false;}
     
     memcpy(backup, used, sizeof used);
     
     
     //b是算出来的，所以b的数字是没用用到过的
     
     //因为这里要改变used[]数组，递归也在调用used数组那些
     //所以我们要重新创个数组
     
     while(b) 
     {
         int x = b %10; //取出个位数
         b /= 10;
         
         if(! x|| backup[x])
         {
             return false;
         }
         
         backup[x] = true;  //将b中用的数变为真
     }
     
     for(int i = 1; i <= 9; i++)
     {
         if(!backup[i])
         {
             return false;
         }
     }
    return true;
     
}

void dfs_c(int u, int a, int c)
{
    if(u > 9) 
    {
        return;
    }

    if(check(a, c))
    {
        ans++;
    }
    
    
    for(int i = 1;i <= 9; i++)
    {
        if(!used[i])
        {
            used[i] = true;
            dfs_c(u + 1, a, c * 10 + i);
            used[i] = false;         
        }
    }
}   

void dfs_a(int u, int a)
{
    if(a >= n) {return;}
    if(a) {dfs_c(u, a, 0);}
    
    for(int i = 1; i <= 9; i++)
    {
        if(!used[i])
        {
            used[i] = true;
            num[u] = i;
            
           dfs_a(u + 1, a * 10 + i );
            
            used[i] = false;
            
        }
    }
}



int main()
{
    
    scanf("%d", &n);
    dfs_a(0, 0);
    
    cout << ans << endl;
    
    return 0;
    
}

费解的开关

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

费解的开关，这道题的话，采用暴力的方法。一个开关2种状态：(选与不选)
，因为要求最优的，一个灯改变，它的上下左右相邻的回改变

解题思路：
所以我们先枚举第一行所有的情况 2^32 = 32,然后选择最优的情况
第一行枚举之后，后面依次枚举(利用下一行选开关，来改变上一行开关的状态)，
但是要留下最后一行(因为最后一行，就没有下一行来改变这一行的状态了)，然后检查这一行的状态
如果全是开的，说明这一行都打开了，说明这种枚举方式成功，记录下步数(与之前的比较，选择最优的)
如果不是全部开的，那么就说明枚举失败，进行下一次循环

代码部分细节讲解：

  1. i >> j & 1
    这里其实用的是二进制的形式表示开关，对开关进行的一种优化
    注意：结果的1与0，不表示开关的状态， 结果如果是1表示开关要按，为0表示开关不按
    例如： 如果i为 00001， j为0， 右移0位表示00001，然后和1进行&运算，结果为1，表示开关(00001,从右往左看)，第一个位置要按，j = 1, j = 2…，都表示不按，所以在开关00001这种枚举情况中，按第一个开关就行，其余开关不用按

2.这里开关状态的变化，采用的枚举的方式
3.注意每种枚举情况，都得把数据拷贝下，然后还原初始状态

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;


const int N = 6;

char g[N][N], backup[N][N]; //题目要求一组5个字符， 所以是char类型


int dx[5] = {0,-1 , 1, 0, 0}, dy[5] = {0, 0, 0, -1, 1};

void turn(int x, int y)
{
    for(int i = 0; i < 5; i++)
    {
        //四周的开关状态改变
        int a = x + dx[i];
        int b = y + dy[i];
        
        if(a >= 0 && a < 5 && b >=0 &&  b < 5)
        {
            g[a][b] ^= 1;  //用异或来进行状态的改变
        }
    }
}

int main()
{
    int T;
    cin >> T;
    
    while(T--)
    {
        for(int i = 0; i < 5; i++)
        {
           cin >> g[i];
        }
        
        int res = 10; // 题目要求步数小于6，这里用来存每种枚举情况更新的步数
        
       
        
        //枚举第一行32种情况
        for(int i = 0; i < 1 << 5 ; i++)
        {
            int step = 0;
             
            memcpy(backup, g, sizeof g);
            for(int j = 0; j < 5; j++)  
            {

                if(i >> j & 1)
                {
                    step++;
                    turn(0, j); 
                }
            }
            
            //剩下几行(除了最后一行)
            for(int i = 0; i < 4; i++)
             {
                for(int j = 0; j < 5; j++)
                {
                    if(g[i][j] == '0')
                    {
                        step++;
                        turn(i + 1, j); // 让上一行的打开   
                    }
                }
            }
        
        //检查最后一行是否全部都开了
            bool dark = false;  //判断是否关了
        
            for(int i = 0; i < 5; i++)
            {
                if(g[4][i] == '0' )
                {
                    
                    dark = true;
                    break;
                }
            }
        
            if(!dark) //最后一行全开了，比较那个步骤少 ，res更新结果
            {
                //printf("res = %d , step = %d\n", res, step);
                res = min(res, step);  
            }
            memcpy(g, backup,sizeof backup);
        }
        
         if(res > 6) 
        {
            cout << -1 << endl;
        }
        else
        {
            cout << res << endl;
        }
    }
    
    return 0;
}

飞行员兄弟

在这里插入图片描述

在这里插入图片描述

这题的思路，跟上题费解的开关，思路差不多，不同的是上题是枚举第一行数据找最优
因为这个开关变化之后，这个开关对应的这一行，这一列都会变化，因为数据不多，
所以可以全部开关都进行暴力枚举

也是采用二进制数进行优化
枚举之后，在判断是否符合条件，当然这里需要我们输出每次改变开关的位置
我这里用vector存储的，pair类型<int, int>

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>

#define x first
#define y second

using namespace std;

const int N = 5;
char g[N][N], backup[N][N];

//返回位置
int get(int x, int y)
{
    return x * 4 + y;
}

void turn_one(int x, int y)
{
    if(g[x][y] == '+')
    {
        g[x][y] = '-';
    }
    else
    {
        g[x][y] = '+';
    }
}

void turn_all(int x, int y)
{
    for(int j = 0; j < 4; j++)
    {
        turn_one(x, j);
        turn_one(j, y);
    }
    //本身翻了2次，相当于没翻，所以还得翻一次
    turn_one(x, y);
}


int main()
{
    
    for(int i = 0; i < 4; i++)
    {
        for(int j = 0; j < 4; j++)
        {
            cin >> g[i][j];
        }
    }
    
    vector<pair<int, int>> result;
    
    //枚举出所有的情况
    for(int pos = 0 ; pos < 1 << 16; pos++)
    {
        vector<pair<int, int>> temp;

        memcpy(backup, g, sizeof g);     
     
        for(int i = 0; i < 4; i++)
        {
            for(int j = 0; j < 4; j++)
            {
                if(pos >> get(i, j) & 1)  //二进制的形式，为1表示需要按， 注意:这里的get(i, j) 要求得具体翻那几个位置
                {
                    temp.push_back({i, j});
                    turn_all(i, j);                
                }
            }
        }
        
        bool has_closed = false;
        
        //看是否所有的灯都开了
        for(int i = 0; i < 4; i++)
        {
            for(int j = 0; j < 4; j++)
            {
                if(g[i][j] == '+')
                {
                    has_closed = true;
                    break;
                }
            }
        }
        
        if(!has_closed)
        {
            if(result.empty() || result.size() > temp.size())
                {
                    result = temp;
                }
        }
        
        memcpy(g, backup, sizeof backup);
    }
    
    cout << result.size() << endl;
        
    for(auto v : result)
    {
        cout << v.first + 1 << " " << v.second + 1 << endl;
    }
    
    return 0;
}

翻硬币

在这里插入图片描述在这里插入图片描述

这题的话，虽然看着代码简单，但是也还是需要我们自己模拟下情况，才做的出来
判断开关的状态的话，前n- 1个就行，第n个肯定一样，因为题干说肯定有解

#include<iostream>
#include<cstdio>
#include<string>

using namespace std;

string a, b;

void turn(int x)
{
    if(a[x] == 'o')
    {
        a[x] = '*';
    }
    else
    {
        a[x] = 'o';
    }
    
}

int main()
{
    
    cin >> a >> b;

    int count = 0;
    
    //前n- 1个就行，第n个肯定一样，因为题干说肯定有解
    for(int i = 0; i < a.size() - 1; i++)
    {
        if(a[i] != b[i])
        {
            count++;
            turn(i);
            turn(i + 1);
        }
    }
    cout << count << endl;
    
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/151718.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Linux常用命令——bzdiff命令

Linux常用命令——bzdiff命令

在线Linux命令查询工具 bzdiff 直接比较两个.bz2压缩包中文件的不同 补充说明 bzdiff命令用于直接比较两个“.bz2”压缩包中文件的不同&#xff0c;省去了解压缩后再调用diff命令的过程。 语法 bzdiff(参数)参数 文件1&#xff1a;指定要比较的第一个.bz2压缩包&#xf…
阅读更多...
《洛谷深入浅出基础篇》P1536 村村通——并查集

《洛谷深入浅出基础篇》P1536 村村通——并查集

上链接&#xff1a;P1536 村村通 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1536 上题干&#xff1a; 题目描述 某市调查城镇交通状况&#xff0c;得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 "村村通工程…
阅读更多...
全民运动时代，气膜建筑备受瞩目

全民运动时代，气膜建筑备受瞩目

气膜体育场馆&#xff0c;作为当今新型的临时建筑运动场馆&#xff0c;在满足大型体育赛事需求方面展现出显著的优势。相较于传统体育场馆&#xff0c;气膜建筑不仅拥有更宽敞的空间&#xff0c;而且造价成本更为经济&#xff0c;成为体育场馆领域备受关注的建筑形式。 气膜建筑…
阅读更多...
郑州市管城区工信局局长任华民一行莅临中创算力调研指导工作

郑州市管城区工信局局长任华民一行莅临中创算力调研指导工作

2023年11月15日&#xff0c;为深入了解企业生产经营情况&#xff0c;解决发展诉求。郑州市管城区工信局局长任华民等领导一行莅临中创算力&#xff0c;中创副总经理杨光、技术总监刘朝阳、行政主管生田等人员陪同调研。 调研期间&#xff0c;双方就生产经营、“算力数据中心”…
阅读更多...
基于SSM的校园二手物品交易市场设计与实现

基于SSM的校园二手物品交易市场设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;Vue 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#xff1a;是 目录…
阅读更多...
界面组件DevExpress Reporting v23.1亮点 - 全新升级报表查看器

界面组件DevExpress Reporting v23.1亮点 - 全新升级报表查看器

DevExpress Reporting是.NET Framework下功能完善的报表平台&#xff0c;它附带了易于使用的Visual Studio报表设计器和丰富的报表控件集&#xff0c;包括数据透视表、图表&#xff0c;因此您可以构建无与伦比、信息清晰的报表 界面组件DevExpress Reporting v23.1已经发布一段…
阅读更多...
如何快速找到华为手机中下载的文档

如何快速找到华为手机中下载的文档

手机的目录设置比较繁杂&#xff0c;尤其是查找刚刚下载的文件&#xff0c;有时候需要捣鼓半天&#xff0c;如何快速找到这些文件呢&#xff1f;以下提供了几种方法&#xff1a; 方法一&#xff1a; 文件管理-》搜索文档 方法二&#xff1a; 文件管理-》最近 方法三&#xf…
阅读更多...
BMS系统项目

BMS系统项目

1、通过电压监测是否冲满&#xff0c;通过电压可以监测是否放完电 电池得参数 单体过压&#xff08;充满电&#xff09; 过压恢复&#xff08;百分之90多&#xff09; 欠压保护&#xff08;百分之几得电&#xff0c;快关机了&#xff09; 欠压恢复&#xff08;就是欠压之上…
阅读更多...
阿里云轻量应用服务器特价87元和165元1年测评，看看是否值得购买

阿里云轻量应用服务器特价87元和165元1年测评，看看是否值得购买

2023年11月&#xff0c;阿里云推出了两款特价轻量应用服务器&#xff0c;2核2G4M特惠价格只要87元1年&#xff0c;2核4G5M特惠价格只要165元1年&#xff0c;那么这两款轻量应用服务器到底怎么样呢&#xff1f;可以用来做什么&#xff1f;是否值得购买呢&#xff1f;下面我们一起…
阅读更多...
（四）什么是Vite——冷启动时vite做了什么（源码、middlewares）

（四）什么是Vite——冷启动时vite做了什么（源码、middlewares）

vite分享ppt&#xff0c;感兴趣的可以下载&#xff1a; ​​​​​​​Vite分享、原理介绍ppt 什么是vite系列目录&#xff1a; &#xff08;一&#xff09;什么是Vite——vite介绍与使用-CSDN博客 &#xff08;二&#xff09;什么是Vite——Vite 和 Webpack 区别&#xff0…
阅读更多...
python递归求数字各个位数相加_和

python递归求数字各个位数相加_和

python递归求数字的各项和&#xff0c;例如数字一千零二十四&#xff1a;“1024”&#xff0c;输出结果为“10247” 第一种方法&#xff1a; def sum(a): #求一个数字各项和&#xff0c;第一种递归方法if 0<a<9: #从前到最后一个&#xff0c;出循环…
阅读更多...
swiper垂直方向全屏实现鼠标滚轮滚动一下切换一屏

swiper垂直方向全屏实现鼠标滚轮滚动一下切换一屏

效果 20231116092014 添加mousewheelControl: true,这个属性即可 <div class"swiper-container"><div class"swiper-wrapper"><div class"swiper-slide" > <div class"" style"height: 100%; background-…
阅读更多...
一个前端非侵入式骨架屏自动生成方案

一个前端非侵入式骨架屏自动生成方案

目录 背景 现有方案调研 侵入业务式手写代码 非侵入业务式手写代码 非侵入式骨架屏代码自动生成 技术方案 设计原则 架构图 骨架屏生成 骨架屏注入 优化点 部分技术细节解析 puppeteer 文本块处理 图片块处理 a 标签处理 自定义属性处理 首屏HTML处理 首屏样…
阅读更多...
合肥数字孪生赋能工业制造，加速推进制造业数字化转型

合肥数字孪生赋能工业制造，加速推进制造业数字化转型

聚焦国家战略需求和先进制造业发展方向&#xff0c;加快数字化发展战略部署&#xff0c;数字孪生、工业互联网、工业物联网已被广泛认为是工业革命的新引擎。合肥数字孪生正在推动工业制造从制造转向智造。通过数字化建模和仿真的方式&#xff0c;优化设计、生产、质量管理、供…
阅读更多...
使用 Gradle 命令了解项目构建信息

使用 Gradle 命令了解项目构建信息

引言 首先&#xff0c;Gradle 作为使用 Android Studio 开发 Android 项目的默认构建工具&#xff0c;它里面的任何东西都基于两个概念&#xff1a; projects ( 项目 )tasks ( 任务 ) 每一个构建由一个或多个 projects 构成&#xff0c;每一个 project 由一个或多个 tasks 构…
阅读更多...
SOLIDWORKS功能布局实用技巧之保存实体技术

SOLIDWORKS功能布局实用技巧之保存实体技术

在SOLIDWORKS软件中&#xff0c;有一些命令可以将一个或多个实体保存为独立的零件文件。然而&#xff0c;每个命令都具有不同的特性&#xff0c;有些命令的选项可以让您在保存多个零件时直接生成装配体文件。让我们来深入了解这些功能布局技巧&#xff0c;特别是实体保存技术。…
阅读更多...
XXX系统测试报告测试用例模板

XXX系统测试报告测试用例模板

XXX系统测试报告 编制&#xff1a; 2023-5-16 审核&#xff1a; 日期&#xff1a; 批准&#xff1a; 日期&#xff1a; 版本 修订时间 修订人 修订类型 修订章节 修订内容 *修订类型分为 A …
阅读更多...
如何解决3d max渲染效果图全白这类异常问题？

如何解决3d max渲染效果图全白这类异常问题？

通过3d max渲染效果图时&#xff0c;经常会出现3Dmax渲染效果图全黑或是3Dmax渲染效果图全白这类异常问题。可能遇到这类问题较多的都是新手朋友。不知如何解决。 3dmax渲染出现异常的问题&#xff0c;该如何高效解决呢&#xff1f;今天小编这里整理几项知识点&#xff0c;大家…
阅读更多...
力扣刷题篇之数与位1

力扣刷题篇之数与位1

系列文章目录 目录 系列文章目录 前言 一、进制转换 总结 前言 本系列是个人力扣刷题汇总&#xff0c;本文是数与位。刷题顺序按照[力扣刷题攻略] Re&#xff1a;从零开始的力扣刷题生活 - 力扣&#xff08;LeetCode&#xff09; 一、进制转换 67. 二进制求和 - 力扣&…
阅读更多...
二十、泛型（8）

二十、泛型（8）

本章概要 潜在的类型机制 pyhton 中的潜在类型C 中的潜在类型Go 中的潜在类型java 中的直接潜在类型 潜在类型机制 在本章的开头介绍过这样的思想&#xff0c;即要编写能够尽可能广泛地应用的代码。为了实现这一点&#xff0c;我们需要各种途径来放松对我们的代码将要作用的…
阅读更多...
最新文章

Copyright @ 2022~2023