作者????♂?：讓機器理解語言か
專欄??：藍橋杯倒計時沖刺
描述??：藍橋杯沖刺階段，一定要沉住氣，一步一個腳印，勝利就在前方！
寄語??：??沒有白走的路，每一步都算數(shù)！??
題目一：數(shù)的計算?
題目描述
我們要求找出具有下列性質(zhì)數(shù)的個數(shù)(包含輸入的自然數(shù) n):
先輸入一個自然數(shù) n?(n≤1000),然后對此自然數(shù)按照如下方法進行處理:
不作任何處理;
在它的左邊加上一個自然數(shù),但該自然數(shù)不能超過該數(shù)最高位的一半;
加上數(shù)后,繼續(xù)按此規(guī)則進行處理,直到不能再加自然數(shù)為止。
輸入描述
輸入一個正整數(shù)?n。
輸出描述
輸出一個整數(shù)，表示具有該性質(zhì)數(shù)的個數(shù)。。
輸入輸出樣例
輸入
6輸出
6
樣例分析?
例: n=6，合法的數(shù)字有: 6(不做任何處理) 、16、26、36、126、136?
解題思路
?按照題目意思，我們可以直接枚舉左邊加的數(shù)。
遞歸
定義遞歸函數(shù)?f(n)?表示輸入數(shù)為?n?時滿足題目條件的數(shù)的個數(shù)。
我們可以從最簡單的情況開始考慮。當?n=1?時，1的一半向下取整為0，沒辦法構造，直接返回。
如果?n>1，那么我們需要枚舉左邊加的數(shù)。因為最左邊的數(shù)不能為?0，所以左邊加上的數(shù)的取值范圍是?[1,?n/2?]。
?對于每一個加數(shù)?i，得到的新數(shù)是?n+i，我們需要遞歸調(diào)用?f(n+i)，計算得到新數(shù)下滿足條件的數(shù)的個數(shù)。
在遞歸調(diào)用結束后，我們需要將所有加數(shù)得到的滿足條件的數(shù)的個數(shù)相加，得到最終的結果。
最后，輸出?f(n)?即可。
遞推?
?AC_code（遞歸）
def f(n):
global res
if n == 1: # 1的一半向下取整為0，沒辦法構造，直接返回
return
for i in range(1, n//2+1): # 枚舉左邊加的數(shù)，其中n//2：向下取整
res += 1
f(i) # 遞歸
n = int(input())
res = 1
f(n)
print(res)??AC_code（遞推）
n = int( input( ))
f = [0 for i in range(n+1)]
for i in range( 1, n + 1): # 從f[1]開始算
for j in range(1, i//2 + 1): # 累加
f[i]= f[i] + f[j] # 遞推式
f[i] += 1 # 自己本身
print(f[n])題目二：數(shù)的劃分?
題目描述
將整數(shù)?n?分成?k?份，且每份不能為空，任意兩份不能相同(不考慮順序)。
例如：n=7，k=3，下面三種分法被認為是相同的。
1，1，5;1，5，1;5，1，1;
問有多少種不同的分法。
輸入描述
輸入一行，2?個整數(shù) n,k?(6≤n≤200，2≤k≤6)。
輸出描述
輸出一個整數(shù)，即不同的分法。
輸入輸出樣例
輸入
7 3輸出
4
?解題思路
定義遞歸函數(shù)?f(n,m)?為將整數(shù)?n?拆分成?m?個數(shù)字的方案數(shù)。
對于每個情況，我們可以將它分成兩種情況，且這兩種情況是不重不漏的。
- 不選 1 的情況：
如果不選擇 1，我們將?n?拆分成?m?塊，可以等價于將每一塊都減去 1，然后再將剩下的數(shù)拆分成?m?塊，即?f(n?m,m)。
- 選 1 的情況：
這種情況下，其中一塊肯定有一個 1，然后對?n?1?拆分成?m?1?塊，即?f(n?1,m?1)。
此時，f(n,m)?的值就是這兩種情況之和，即f(n,m)=f(n?m,m)+f(n?1,m?1)
需要注意的是，當 n<m 時，無法分成 m 個數(shù)，因此 f(n,m) = 0
另外，當 m=1 時，只能將 n 拆分成一個數(shù)，因此 f(n,1) = 1；當n=m時，只能是每塊1個，所以f(i, i)=1
最終的答案為 f(n,k) 。
AC_code?
由于 python遞歸的速度極慢，因此我們可以使用動態(tài)規(guī)劃的思想，將遞歸改為遞推，代碼如下：?
n, k = map(int, input().split())
# 初始化一個二維數(shù)組，用于存儲 f(n, m)
dp = [[0 for j in range(210)] for i in range(210)]
for i in range(1, n+1):
dp[i][1] = 1
dp[i][i] = 1
for i in range(3, n+1):
for j in range(2, k+1):
if i > j: # 只有n大于m才能分出多種情況
dp[i][j] = dp[i-j][j] + dp[i-1][j-1]
print(dp[n][k])題目三：耐摔指數(shù)?
題目描述
X 星球的居民脾氣不太好，但好在他們生氣的時候唯一的異常舉動是：摔手機。
各大廠商也就紛紛推出各種耐摔型手機。X 星球的質(zhì)監(jiān)局規(guī)定了手機必須經(jīng)過耐摔測試，并且評定出一個耐摔指數(shù)來，之后才允許上市流通。
X 星球有很多高聳入云的高塔，剛好可以用來做耐摔測試。塔的每一層高度都是一樣的，與地球上稍有不同的是，他們的第一層不是地面，而是相當于我們的 2 樓。
如果手機從第 7 層扔下去沒摔壞，但第 8 層摔壞了，則手機耐摔指數(shù) = 7。
特別地，如果手機從第 1 層扔下去就壞了，則耐摔指數(shù) = 0。
如果到了塔的最高層第?n?層扔沒摔壞，則耐摔指數(shù) =?n。
為了減少測試次數(shù)，從每個廠家抽樣 3 部手機參加測試。
如果已知了測試塔的高度，并且采用最佳策略，在最壞的運氣下最多需要測試多少次才能確定手機的耐摔指數(shù)呢？
輸入描述
一個整數(shù) n（3<n<10000）,表示測試塔的高度。
輸出描述
輸出一個整數(shù)，表示最多測試多少次。
輸入輸出樣例
輸入
3輸出
2樣例解釋
手機?a?從 2 樓扔下去，壞了，就把?b?手機從 1 樓扔；否則?a?手機繼續(xù) 3 層扔下。
?解題思路
????????設?bi??表示需要?i?個球時最少要有多少層樓，ci??表示最少需要多少個球才能測出?i?層樓，初始化?b1?=c1?=1，由于球的數(shù)量不會超過?100100，故開數(shù)組?b?和?c?大小均為?105105。
????????當需要測的樓層數(shù)為?n?時，從?11?開始枚舉，如果?ci??大于等于?n，那么?i?即為需要的最少球的數(shù)量，輸出后退出。
????????當?ci??小于?n?時，需要再增加一個球，求出測?i+1?層樓所需的最小樓層數(shù)?bi+1??和測?i+1?層樓所需的最少球數(shù)?ci+1?，由于測第?i+1?層樓時，要么球碎了，要么沒碎，因此：文章來源：http://www.zghlxwxcb.cn/news/detail-406136.html
- 如果球碎了，需要在樓下測?bi??層樓，此時用剩下的?i?1?個球去測樓下的這?bi??層樓，共需要?i?個球，即?ci+1?=ci?+i。
- 如果球沒碎，需要在上面測剩下的?i?個球，即去測?i?1?層樓，此時共需測?i+1?層樓，需要在樓上再增加一層樓，因此用剩下的?i?1?個球去測這?i?層樓，共需要?bi??層樓，即?ci+1?=ci?+bi?+1。
因此得到遞推公式：bi+1?=bi?+i+1；ci+1?=ci?+bi?+1文章來源地址http://www.zghlxwxcb.cn/news/detail-406136.html
?AC_code
b = [0] * 105
c = [0] * 105
n = int(input())
i = 0
while c[i] < n:
i += 1
b[i] = i + b[i - 1]
c[i] = c[i - 1] + b[i - 1] + 1
print(i)到了這里，關于藍橋杯倒計時 | 倒計時4天的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
