当前位置:网站首页>Niuke real problem programming - Day17
Niuke real problem programming - Day17
2022-07-07 14:53:00 【weixin_ forty-five million seven hundred and fifty thousand fou】
Compile environment :c++
1、 Shooting game
describe :
There is a shooting game . The court has p A basket , The number is 0,1...,p-1. There is a bag under each basket , Each bag can hold at most one basketball . Yes n A basketball , Each ball number xi . The rule is to set the number to xi Our basketball shot xi except p The remainder of is in the numbered bag . If there is basketball in the bag, the ball pops up and the game ends i, Otherwise repeat until all shots are thrown . Output -1. Ask what the final output of the game is ?
Algorithmic thought :
The topic idea is actually very simple , Just simulate the whole process , And the title doesn't seem to explain the number of the ball i It's from 1 At the beginning , Attention should be paid to when outputting results . my bug It's typing n When the ball hits , Input and processing are put together , It took a long time to debug at the beginning , Because the game may end when processing , But the input of the use case is not completely over , Resulting in the following result error . Finally, I chose to separate two cycles , The value of each input ball is summed , The number of balls accumulating the same remainder , When the number is no longer 1 when , You can interrupt the game . If it ends naturally , You can declare an extra bool Quantity to determine whether output -1 identification .
2、 Minimum quantity of goods packed
describe :
The weights are 3,5,7 Three kinds of goods in kilograms , And a payload of X Kilogram boxes ( Regardless of volume and other factors , Only calculate the weight )
Need to fill the box X Kilogram cargo , It is required to use as few goods as possible ( The quantity of three kinds of goods is unlimited )
Data range : 1≤x≤10000
Algorithmic thought :
The problem is actually a knapsack problem of dynamic programming . set up dp[i] by i The minimum number of goods per kilogram , that dp[i] It must be equal to i-3,i-5,i-7 The minimum quantity of three kilograms +1 Minimum of , Then we can get the recurrence equation of dynamic programming , namely dp[i] = min(min(dp[i-3],dp[i-5]),dp[i-7])+1. First of all to dp3、5、6、7 The initialization , Then call recursive .
The code part implements :
3、 Go up the steps
describe :
There is a staircase for m level , At first you were at the first level , If you can only step up one or two levels at a time , To go on m level , How many ways are there ? notes : It is stipulated that from level one to level one there are 0 Seed walking method .
Given a positive integer int n, Please return a number , Number of ways to go upstairs . Guarantee n Less than or equal to 100. To prevent spillage , Please return the result Mod 1000000007 Value .
Algorithmic thought :
This problem is also dynamic programming . set up dp[i] by i The number of steps , Decomposition subproblems have m The steps can only be taken from m-1/m-2 Step up , Because I can only walk every time 1/2 Steps . So we can get the recursion of this problem dp[i]=(dp[i-1]+dp[i-2]). Remember to initialize dp[1]、2、3 Initial value of , And consider the problem of data overflow .
The code part implements :
边栏推荐
- Instructions d'utilisation de la trousse de développement du module d'acquisition d'accord du testeur mictr01
- Instructions for mictr01 tester vibrating string acquisition module development kit
- Novel Slot Detection: A Benchmark for Discovering Unknown Slot Types in the Dialogue System
- Five pain points for big companies to open source
- PAG体验:十分钟完成AE动效部署上线各平台!
- electron remote 报错
- [Yugong series] go teaching course 005 variables in July 2022
- 大厂做开源的五大痛点
- "July 2022" Wukong editor update record
- AWS learning notes (III)
猜你喜欢
Niuke real problem programming - day15
leetcode:648. Word replacement [dictionary tree board + find the shortest matching prefix among several prefixes]
Cvpr2022 | backdoor attack based on frequency injection in medical image analysis
「2022年7月」WuKong编辑器更版记录
MySQL installation configuration 2021 in Windows Environment
C# 6.0 语言规范获批
15、文本编辑工具VIM使用
Niuke real problem programming - Day11
The world's first risc-v notebook computer is on pre-sale, which is designed for the meta universe!
13 ux/ui/ue best creative inspiration websites in 2022
随机推荐
寺岗电子称修改IP简易步骤
Cvpr2022 | backdoor attack based on frequency injection in medical image analysis
华为云数据库DDS产品深度赋能
暑期安全很重要!应急安全教育走进幼儿园
Andriod --- JetPack :LiveData setValue 和 postValue 的区别
CPU与chiplet技术杂谈
Mlgo: Google AI releases industrial compiler optimized machine learning framework
Concurrency Control & NoSQL and new database
Novel Slot Detection: A Benchmark for Discovering Unknown Slot Types in the Dialogue System
Ffmpeg --- image processing
WebRTC 音频抗弱网技术(上)
Protection strategy of server area based on Firewall
半小时『直播连麦搭建』动手实战,大学生技术岗位简历加分项get!
Es log error appreciation -- allow delete
电脑Win7系统桌面图标太大怎么调小
Niuke real problem programming - Day12
PD虚拟机教程:如何在ParallelsDesktop虚拟机中设置可使用的快捷键?
Niuke real problem programming - day14
Pytorch model trains practical skills and breaks through the bottleneck of speed
因员工将密码设为“123456”,AMD 被盗 450Gb 数据?