首页 > 编程语言 >信息学奥赛初赛天天练-86-NOIP2014普及组-基础题5-球盒问题、枚举算法、单源最短路、Dijkstra算法、Bellman-Ford算法

信息学奥赛初赛天天练-86-NOIP2014普及组-基础题5-球盒问题、枚举算法、单源最短路、Dijkstra算法、Bellman-Ford算法

时间:2024-09-08 13:03:48浏览次数:8  
标签:Dijkstra Bellman Ford 算法 袋子 初赛 枚举

信息学奥赛初赛天天练-86-NOIP2014普及组-基础题5-球盒问题、枚举算法、单源最短路、Dijkstra算法、Bellman-Ford算法
PDF文档公众号回复关键字:20240908

1 NOIP 2014 普及组 基础题5

21 把 M个同样的球放到 N个同样的袋子里,允许有的袋子空着不放,问共有多少种不同的放置方法?

(用 K表示)( )

例如,M=7,N=3 时,K=8;在这里认为 (5,1,1)和 (1,5,1)是同一种放置方法。

问:M=8,N=5时,K=( )

22 如图所示,图中每条边上的数字表示该边的长度,则从A到E的最短距离是

2 相关知识点

1) 枚举算法

枚举法是训练我们逻辑思维严密性的一种数学逻辑

在计算的过程中,我们一定要遵循枚举法的思路,把所有的情况,按照一定的顺序,一一列举出来

所以我们在学习枚举法的时候,一定要从小到大一一列举,不重不漏

例题

有红色和蓝色两种文具盒,小黄人要把8只相同的铅笔放到这两个文具盒中,每个文具盒至少放一支铅笔,那么一共有多少种不同的方法?

答案 7种

分析

红色和蓝色总共8只

每个文具盒子至少一只,固定红色最少1只,最多7只,从红色从小到大顺序枚举,可以做到不重不漏

总共有红色和蓝色2种,红色固定后,蓝色也固定了

红色  蓝色
 1    7
 2    6
 3    5
 4    4
 5    3
 6    2
 7    1

2) 单源最短路

单源最短路算法计算了图论中的一个经典问题,给出从给定的一个节点(称为源节点)出发到其余各节点的最短路径长度。

单源最短路算法适用于网络路由、路径设计等场景。Bellman-Ford算法和Dijkstra算法都是求解图的最短路径的算法

Dijkstra算法

Dijkstra算法的特点主要是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法采用的是贪心策略,其基本算法思想是指定起点s,再引进2个集合S和U,S用来记录已经找到最短路径的顶点,而U里包含未找到最短路径的顶点。系统不断地找出路径最短的顶点,并且将其移出U集,加入S集中。初始时S为空集,U集包含全部顶点,系统不断执行,遍历完所有顶点后,U集更新为空集,任务结束。

Bellman-Ford算法

Bellman-Ford算法的原理是连续地进行松弛,在每次松弛时更新每条边,若在n-1次松弛后还能更新,说明图中有负环,因此无法得出结果,否则任务完成。Bellman-Ford算法首先计算除源点外的所有顶点的最短距离估计值,然后对边集中的每条边进行松弛操作,使得每个顶点距离源点的最短距离估计值逐渐逼近其实际的最短距离

3 思路分析

21 把 M个同样的球放到 N个同样的袋子里,允许有的袋子空着不放,问共有多少种不同的放置方法?

(用 K表示)( )

例如,M=7,N=3 时,K=8;在这里认为 (5,1,1)和 (1,5,1)是同一种放置方法。

问:M=8,N=5时,K=( 18 )

分析

枚举-非递减整数枚举
允许空着不放
5个袋子,可以放1个袋子,空4个袋子
8
总共1种

5个袋子,可以放2个袋子,空3个袋子
1 7
2 6
3 5
4 4
总共4种

5个袋子,可以放3个袋子,空2个袋子
1 1 6
1 2 5
1 3 4
2 2 4
2 3 3
总共5种

5个袋子,可以放4个袋子,空1个袋子
1 1 1 5
1 1 2 4
1 1 3 3
1 2 2 3
2 2 2 2
总共5种

5个袋子,可以放5个袋子,空0个袋子
1 1 1 1 4
1 1 1 2 3
1 1 2 2 2
总共3种

22 如图所示,图中每条边上的数字表示该边的长度,则从A到E的最短距离是( 11 )

分析

从A出发,和A相邻的点为B,G,F,到B最短,长度为3
从A-B出发,和C,D相邻,到C最短,长度为3+1=4
从A-C出发,和E,F,G相邻,到F最短,长度为4+1=5
从A-F出发,和D,E相邻,到D最短,长度为5+2=7
从A-F出发,和D,E相邻,到E的长度为5+6=11
从A-D出发,到E距离为4,长度为7+4=11
所以最短距离为11

标签:Dijkstra,Bellman,Ford,算法,袋子,初赛,枚举
From: https://www.cnblogs.com/myeln/p/18402771

相关文章

  • 算法入门-深度优先搜索2
    第六部分:深度优先搜索104.二叉树的最大深度(简单)题目:给定一个二叉树root,返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。示例1:输入:root=[3,9,20,null,null,15,7]输出:3示例2:输入:root=[1,null,2]输出:2第一种思路:感觉递......
  • 马老师浑元十三刀本质是DDD程序=算法+数据结构:浑元形意太极的本质是领域驱动设计(02)
    浑元形意太极的本质是领域驱动设计(01)在软件开发的旅程中,领域驱动设计就是我们的指路明灯。它照亮了我们前进的道路,驱散了迷茫的阴霾。有了领域驱动设计的指引,我们不再畏惧未知,不再害怕挑战。我们知道,无论前方有多么艰难的障碍,都有领域驱动设计为我们指明方向。领域驱动设计就......
  • [USACO3.2] 香甜的黄油 Sweet Butter(Dijkstra)
     FarmerJohn发现了做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道NNN只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然,他将付出额外的费用在奶牛上。FarmerJohn很狡猾。像以前的Pavlov,他知道他可以训练这些奶牛,让它们在听到铃声时去一个特......
  • 猎豹算法(CO)优化BP神经网络原理及Matlab代码
    目录0引言1数学模型2优化方式3Maltab代码3.1伪代码3.2CO主函数代码3.3CO-BP4视频讲解0引言猎豹算法(cheetahoptimizer,CO)是MohammadAminAkbari于2022年基于猎豹的狩猎策略启发而提出的智能算法。CO模拟猎豹的三种主要策略来捕猎猎物,即搜索、坐着和攻击;同时......
  • 猎豹算法(CO)优化支持向量机原理及Matlab代码
    目录0引言1数学模型2优化方式3Maltab代码3.1伪代码3.2CO主函数代码3.3CO-SVM4视频讲解0引言猎豹算法(cheetahoptimizer,CO)是MohammadAminAkbari于2022年基于猎豹的狩猎策略启发而提出的智能算法。CO模拟猎豹的三种主要策略来捕猎猎物,即搜索、坐着和攻击;同时......
  • 猎豹算法(CO)优化长短期记忆神经网络原理及Matlab代码
    目录0引言1数学模型2优化方式3Maltab代码3.1伪代码3.2CO主函数代码3.3CO-LSTM4视频讲解0引言猎豹算法(cheetahoptimizer,CO)是MohammadAminAkbari于2022年基于猎豹的狩猎策略启发而提出的智能算法。CO模拟猎豹的三种主要策略来捕猎猎物,即搜索、坐着和攻击;同......
  • 【大数据】分布式数据库算法
    目录一、分布式数据库算法概述二、分布式数据库算法分类2.1分布式数据库算法的优点2.2分布式数据库算法的缺点三、分布式数据库算法实现3.1 分布式数据库算法C语言实现3.2 分布式数据库算法JAVA实现四、分布式数据库算法应用五、分布式数据库算法发展趋势一、......
  • 【智能优化算法】水流优化器(WFO),SCI顶刊,含有MathType公式、伪代码、visio的流程图、m
    该文末包括5个内容:用MathType编辑的公式、伪代码、visio的流程图,matlab代码,PDF论文,拿来直接用,可以帮助科研者省下超多时间。受自然界水流形态的启发,该算法论文作者提出了一种新的全局优化算法——水流优化器(WFO)。发表在顶级SCI期刊IEEETransactionsonCybernetics(影响因......
  • 2024年SCI一区顶刊新算法,包括徒步优化算法(HOA)、常青藤优化算法(Ivy)、黑翅鸢优化算法(B
        文中内容包括徒步优化算法(HOA)、常春藤优化算法(Ivy)、黑翅鸢优化算法(BKA)的用MathType编辑公式、伪代码、matlab代码、PDF论文、latex参考文献引用格式,拿来直接用,帮助科研者省下超多时间。    徒步优化算法(HikingOptimizationAlgorithm,HOA)的灵感来自于徒步......
  • C++编程-搜索与回溯算法2
    目录每日一诗先言正文例题六题目描述算法分析标准程序例题七:选书题目描述算法分析标准程序输出例题八:跳马问题题目描述标准程序小练习题目描述输入输出样例输入 复制样例输出 复制每日一诗红豆生南国,春来发几枝。愿君多采撷,此物最相思。Redbea......