Niuke real problem programming - Day17

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 ：