洛谷题单【算法1-3】暴力枚举 P1157

这篇具有很好参考价值的文章主要介绍了洛谷题单【算法1-3】暴力枚举 P1157。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言(一些想法)

        最近有很多自己想做的事情,但猛地发现自己似乎并没有将课内的课程知识学好,个人规划与学习安排之间似乎出现了不可忽视的冲突,于是上一周自己在无所事事中迷茫地摆了一周。打算从这周开始改变,就从每天坚持发帖子记录自己做题经验开始吧。

题目:

洛谷题单【算法1-3】暴力枚举 P1157,算法,深度优先,图论

关于搜索

        题目的要求其实就是输出  ,可以注意到如果我们考虑输出的数组out,会发现其具有“逐层递增”的特点,不难想到深度优先搜索,即dfs。

        按照我写的 void dfs(int x)形式,通常都是在一定条件下创造一个各部分之间满足特殊层次关系的结构,通常是一种方案或是一组数组,而方案/数组中的每个元素都是需要改变的,并且这种方式会以一种特殊的“递增”关系相连接。

        例如此时有五种商品种类及其对应的价格,要求一次购物方案包含其中的三样商品,并且给出方案的总金额。在这里总金额不是搜索想法的关键,而应该是方案的“创造”。在为商品标上序号后(可以是任意的方式,并不影响),我们可以通过数组或者结构体的方式(本质就是容器)存储商品序号与商品价格,并且按照一种特殊的方法对它们进行取用,这就是个人理解的搜索的思想。

        因为取用的方式多有相似,所以搜索不可避免的需要“递归”;有时候因为已经进行过搜索,希望重新搜索其他元素,所以需要“回溯”;搜索得以与其他思想联系起来。(也许有机会的话,我更想尝试一下视频制作,更好的将我的思想呈现出来,特别是为了自己进行审视反思)

题目分析

        说了这么多搜索相关,还是来看看这道题目吧!

        明明是一个高中数学中十分基础的数学概念,但好像我却并不能轻描淡写的用几行代码就将它描述出来(个人水平有限),这就很有意思了,那当然要分析一下实现过程中的难点在哪里啦!

        仔细想想,原因主要是因为在平时的数学计算中,我们会更倾向于关注组合数的结果,而不是所有方案的具体情况。否则我们只需要同样利用阶乘,代入组合数公式就能得出结果。但既然题目要求我们输出可行的每一种方案,那我们就要模拟组合数中“挑选”的过程来。

        我们在计算组合数的时候,脑子里面其实已经有了一个自然数数组1-n,同时还要有一个数组用来接收一种方案(就好像拿着碗挑水果做水果捞一样)。我们会发现这个过程中透露出来的想法其实就是上文提到的搜索,所以接下来就可以进行实现了。

代码如下:

#include <iostream>
#include <iomanip>
using namespace std;
int n, r;
int out[30];
//dfs(X)传入的x指的是结构的层数!注意了!

void dfs(int x) {
	if (x > r) {
		for (int i = 1;i <= r;i++) {
			cout << setw(3) << out[i];
		}//满足题目要求的占位
		cout << endl;//输出格式,当产生一种方案之后进行换行,易读
		return;
	}
	for (int i = x;i <= x + (n - r);i++) {//找出规律,限定一下初始化和结束条件,可以更加方便
		bool flag = true;
		//这里说一下flag
		//因为我在实现这个的时候,实际上是在完成结构时使用了搜索,但填入元素时我仍然使用循环
		//那么每一个位置都有一个循环区间,就是for语句刚开始的内容
		//因为是组合,要求一组方案中的数没有顺序,即一共出现的数字的情况不能重复
		//于是就利用了循环字典序自动从小到大的特点
		//先选定一个要填入的数,在填入前与已经填入的数相比
		//不但不能等于,而且因为搜索也是不断深入的原因,要保证这个填入的数大于前面出现的所有数
		//采用的是一旦出现就退出循环,并用flag记为异常。如果不是异常退出(即正常循环完)就填入这个数并继续搜索
		//我认为这样可以减少一些循环次数
		for (int j = 1;j < x;j++) {
			if (out[j] >= i) {
				flag = false;
				break;
			}
		}
		if (flag) {
			out[x] = i;
			dfs(x + 1);
		}
	}

}

int main() {
	cin >> n >> r;
	dfs(1);
	return 0;
}

运行结果如图:

5 3
  1  2  3
  1  2  4
  1  2  5
  1  3  4
  1  3  5
  1  4  5
  2  3  4
  2  3  5
  2  4  5
  3  4  5

后记

        题目很基础,写这篇帖子是为了反思一下今天做了什么,想了什么,如何尝试把想法表达出来,进而在这个过程中完成对知识的巩固。也希望以后我无聊翻看博客的时候,能够指出以前代码中的幼稚和不成熟的地方,进而不断成长。文章来源地址https://www.toymoban.com/news/detail-854422.html

到了这里,关于洛谷题单【算法1-3】暴力枚举 P1157的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 洛谷题单 Part 8.2 最短路问题

    最短路算法一般在算法竞赛中有四种比较常见, F l o y d Floyd Fl oy d 算法, B e l l m a n − F o r d Bellman-Ford B e ll man − F or d 算法, D i j k s t r a Dijkstra D ijk s t r a 算法, S P F A SPFA SPF A 算法。 F l o y d Floyd Fl oy d 算法和 B e l l m a n − F o r d Bellman-Ford B e ll man − F or d 算法的时间复杂

    2024年02月09日
    浏览(50)
  • 【DFS专题】深度优先搜索 “暴搜”优质题单推荐 10道题(C++ | 洛谷 | acwing)

    【DFS专题】优质题单推荐 10道题(C++ | 洛谷 | acwing) 来自b站大佬的题单 题单链接 每个位置选什么数 与全排列的差别就是第二个for循环开始的位置,换句话说就是每个数该放什么位置。 参数 : 前u个数 选 or 不选 的 需要保存第x位置的状态的时候就需要用st数组来存状态 i

    2023年04月08日
    浏览(46)
  • C语言,洛谷题,压缩技术2.0

    题目如下:  这题用C语言实现有一些难度,要用到一个库函数,strcat(头文件是string.h),用于连接两个字符串数组,strcat(str,arr)就是将arr字符数组后面的\\0清除,再将arr字符拼接到str上。 题目指出,输入的是一个n*n大小的输入数据,可以先打印第一行后,计算第一行后,计

    2024年02月07日
    浏览(38)
  • 【题单】一个动态更新的洛谷综合题单

    洛谷试炼场的题目确实很具有代表性,但是近几年以来,又有许多经典题目出现在 OI 界中,这个大题单就是作为洛谷试炼场的扩展和补充。 目录 新版本食用指南 更新日志 题单 Part 0 试机题 Part 1 入门阶段 Part 2 基础算法 Part 3 搜索 Part 4 动态规划 Part 4.1-4.4 动态规划 Part 4.5-

    2024年02月19日
    浏览(33)
  • 蓝桥杯双周赛算法心得——三带一(暴力枚举)

    大家好,我是晴天学长,枚举思想,需要的小伙伴可以关注支持一下哦!后续会继续更新的。 1) .三带一 2) .算法思路 1.通过Scanner读取输入的整数n,表示接下来有n个字符串需要处理。 2.使用循环遍历每个字符串: 3.将字符串转换为字符数组c。 4.对于每个字符c[j],统计在整个

    2024年02月07日
    浏览(55)
  • 洛谷-官方题单版【入门篇】

    题目背景 本题是洛谷的试机题目,可以帮助了解洛谷的使用。 建议完成本题目后继续尝试 P1001、P1008。 另外强烈推荐新用户必读贴 题目描述 超级玛丽是一个非常经典的游戏。请你用字符画的形式输出超级玛丽中的一个场景。 题目描述 输入一个小写字母,输出其对应的大写

    2024年02月02日
    浏览(69)
  • 算法 |【实验5.2】1-深度优先搜索暴力求解旅行商问题

    商品推销员要去n个城市推销商品,城市从1至n编号,任意两个城市间有一定距离,该推销员从城市1出发,需要经过所有城市并回到城市1,求最短总路径长度。 把旅行商问题看作一种排列问题,不难想出,这道题的蛮力做法即穷举所有路线。选定起点有n种选法,选定起点后的

    2023年04月08日
    浏览(70)
  • 【蓝桥杯试题】暴力枚举题型

    💃🏼 本人简介:男 👶🏼 年龄:18 🤞 作者:那就叫我亮亮叭 📕 专栏:蓝桥杯试题 有一个 n×m 方格的棋盘,求其方格包含多少正方形、长方形(不包含正方形)。 输入格式 一行,两个正整数 n,m(n ≤ 5000, m ≤ 5000)。 输出格式 一行,两个正整数,分别表示方格包含多少

    2023年04月08日
    浏览(60)
  • 冶炼金属【暴力枚举 + 二分 + 二元不等式】

    😊😊 😊😊 不求点赞,只求耐心看完,指出您的疑惑和写的不好的地方,谢谢您。本人会及时更正感谢。希望看完后能帮助您理解算法的本质 😊😊 😊😊 小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V V V , V V V 是

    2024年02月02日
    浏览(37)
  • 算法题目题单+题解——图论

    本文为自己做的一部分图论题目,作为题单列出,持续更新。 题单由题目链接和题解两部分组成,题解部分提供简洁题意,代码仓库:Kaiser-Yang/OJProblems。 对于同一个一级标题下的题目,题目难度尽可能做到递增。 题目链接:Luogu P3547 [POI2013] CEN-Price List 题解: 题目链接:

    2024年02月19日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包