數(shù)學(xué)

顧名思義，數(shù)學(xué)類的題就是都可以用數(shù)學(xué)知識求解。

買不到的數(shù)目

這是第四屆藍(lán)橋杯省賽C++A組,第四屆藍(lán)橋杯省賽JAVAC組的一道題

小明開了一家糖果店。

他別出心裁：把水果糖包成4顆一包和7顆一包的兩種。

糖果不能拆包賣。

小朋友來買糖的時(shí)候，他就用這兩種包裝來組合。

當(dāng)然有些糖果數(shù)目是無法組合出來的，比如要買 10 顆糖。

你可以用計(jì)算機(jī)測試一下，在這種包裝情況下，最大不能買到的數(shù)量是17。

大于17的任何數(shù)字都可以用4和7組合出來。

本題的要求就是在已知兩個(gè)包裝的數(shù)量時(shí)，求最大不能組合出的數(shù)字。

輸入格式
兩個(gè)正整數(shù) n,m，表示每種包裝中糖的顆數(shù)。

輸出格式
一個(gè)正整數(shù)，表示最大不能買到的糖數(shù)。

數(shù)據(jù)范圍
2≤n,m≤1000，
保證數(shù)據(jù)一定有解。

輸入樣例：

4 7

輸出樣例：

17

這道題簡單看一下，似乎沒有什么規(guī)律，我們可以先打表來找一下規(guī)律：

#include <bits/stdc++.h>

using namespace std;

//給定一個(gè)m，是否能用p和q湊出來
bool dfs(int m,int p,int q)
{
    if(m == 0) return true;

    if(m >= p && dfs(m - p,p,q)) return true;
    if(m >= q && dfs(m - q,p,q)) return true;

    return false;
}

int main()
{
    int p,q;
    cin >> p >> q;
    int res = 0;
    for(int i = 1; i <= 1000;i ++)
    {
        if(!dfs(i,p,q)) res = i;
    }

    cout << res << endl;

    return 0;
}

打表暴力搜索找規(guī)律

2 3 輸出 1
3 5 輸出7
3 7 輸出11
3 10 輸出17
...
最后得到規(guī)律
如果 a,b均是正整數(shù)且互質(zhì)，那么由 ax+by,x≥0,y≥0ax+by,x≥0,y≥0 不能湊出的最大數(shù)是 (a−1)(b−1)−1。

接下來再看數(shù)學(xué)代碼：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int p, q;
    cin >> p >> q;
    cout << (p - 1) * (q - 1) - 1 << endl;

    return 0;
}

螞蟻感冒

這也是藍(lán)橋杯的一道題，來源：第五屆藍(lán)橋杯省賽C++A/B組

長 100 厘米的細(xì)長直桿子上有 n 只螞蟻。

它們的頭有的朝左，有的朝右。

每只螞蟻都只能沿著桿子向前爬，速度是 1 厘米/秒。

當(dāng)兩只螞蟻碰面時(shí)，它們會同時(shí)掉頭往相反的方向爬行。

這些螞蟻中，有 1 只螞蟻感冒了。

并且在和其它螞蟻碰面時(shí)，會把感冒傳染給碰到的螞蟻。

請你計(jì)算，當(dāng)所有螞蟻都爬離桿子時(shí)，有多少只螞蟻患上了感冒。

輸入格式
第一行輸入一個(gè)整數(shù) n, 表示螞蟻的總數(shù)。

接著的一行是 n 個(gè)用空格分開的整數(shù) Xi, Xi 的絕對值表示螞蟻離開桿子左邊端點(diǎn)的距離。

正值表示頭朝右，負(fù)值表示頭朝左，數(shù)據(jù)中不會出現(xiàn) 0 值，也不會出現(xiàn)兩只螞蟻占用同一位置。

其中，第一個(gè)數(shù)據(jù)代表的螞蟻感冒了。

輸出格式
輸出1個(gè)整數(shù)，表示最后感冒螞蟻的數(shù)目。

數(shù)據(jù)范圍
1<n<50,
0<|Xi|<100

輸入樣例1：

3
5 -2 8

輸出樣例1：

1

輸入樣例2：

5
-10 8 -20 12 25

輸出樣例2：

3

這題很有意思，只讀題就會有這種想法，如果一只螞蟻從左往右走，另外一只從右往左走，有一只感冒了，那么，他們相遇后就會分別向相反的方向走。

按照這個(gè)思路，我們來寫一個(gè)暴力解法：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, pos;
int a[N];
int ans = 1;
int cmp(int a, int b)
{
  return abs(a) < abs(b);
}
int main()
{
  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> a[i];
  int pre = a[0];
  sort(a, a + n, cmp); //先按絕對值 將螞蟻的位置排好
  for (int i = 0; i < n; i++)
  {
    if (a[i] == pre)
      pos = i;
  }
  int flag = 0;
  if (pre > 0) //首先感染的螞蟻向右走
  {
    for (int i = pos + 1; i < n; i++)
    {
      if (a[i] > 0)
        continue;
      if (a[i] < 0)
      {
        ans++;
        flag = 1; //標(biāo)記右面有螞蟻向左走
      }
    }
    for (int i = pos - 1; i >= 0; i--)
    {
      if (flag) //在右邊有往左走的螞蟻前提下
      {
        if (a[i] > 0) //如果左面有向右走的那么肯定會傳染
          ans++;
      }
    }
  }
  if (pre < 0)  //首先感染的螞蟻向左走，方法同上
  {
    for (int i = pos - 1; i >= 0; i--)
    {
      if (a[i] < 0)
        continue;
      if (a[i] > 0)
      {
        ans++;
        flag = 1;
      }
    }
    for (int i = pos + 1; i < n; i++)
    {
      if (a[i] > 0)
        continue;
      if (flag)
      {
        if (a[i] < 0)
          ans++;
      }
    }
  }
  cout << ans << endl;

  return 0;
}

但這中間就有一個(gè)很有意思的地方就是左邊的往右走，右邊的往左走，有一只感冒了，它們相遇后還是等價(jià)于有兩只螞蟻分別往前走，只是這樣兩只螞蟻都感冒了，這樣之后遇到的螞蟻也會被感冒，這樣想就不會有掉頭做判斷這一步了，接下來請看代碼：

#include <bits/stdc++.h>

using namespace std;

const int N = 55;

int n;
int x[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> x[i];

    int left = 0, right = 0;    // 分別表示左邊向右走的螞蟻數(shù)量，和右邊向左走的螞蟻數(shù)量
    for (int i = 1; i < n; i ++ )
        if (abs(x[i]) < abs(x[0]) && x[i] > 0) left ++ ;
        else if (abs(x[i]) > abs(x[0]) && x[i] < 0) right ++ ;

    if (x[0] > 0 && right == 0 || x[0] < 0 && left == 0) cout << 1 << endl;
    else cout << left + right + 1 << endl;

    return 0;
}

飲料換購

來源：第六屆藍(lán)橋杯省賽C++A/C組,第六屆藍(lán)橋杯省賽JAVAB組

樂羊羊飲料廠正在舉辦一次促銷優(yōu)惠活動(dòng)。樂羊羊C型飲料，憑3個(gè)瓶蓋可以再換一瓶C型飲料，并且可以一直循環(huán)下去(但不允許暫借或賒賬)。

請你計(jì)算一下，如果小明不浪費(fèi)瓶蓋，盡量地參加活動(dòng)，那么，對于他初始買入的 n 瓶飲料，最后他一共能喝到多少瓶飲料。

輸入格式
輸入一個(gè)整數(shù) n,表示初始買入的飲料數(shù)量。

輸出格式
輸出一個(gè)整數(shù)，表示一共能夠喝到的飲料數(shù)量。

數(shù)據(jù)范圍
0<n<10000

輸入樣例：

100

輸出樣例：

149

這題就很簡單了,還是先看模擬代碼：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int res = n;
    while (n >= 3)
    {
        res += n / 3;
        n = n / 3 + n % 3;
    }

    cout << res << endl;

    return 0;
}

然后是數(shù)學(xué)公式代碼：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    cout << n + (n - 1) / 2 << endl;
    return 0;
}

簡單DP

先來看題：01背包問題是非常經(jīng)典的DP問題。

01背包問題

有 N 件物品和一個(gè)容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的體積是 vi，價(jià)值是 wi。

求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價(jià)值最大。
輸出最大價(jià)值。

輸入格式
第一行兩個(gè)整數(shù)，N，V，用空格隔開，分別表示物品數(shù)量和背包容積。

接下來有 N 行，每行兩個(gè)整數(shù) vi,wi，用空格隔開，分別表示第 i 件物品的體積和價(jià)值。

輸出格式
輸出一個(gè)整數(shù)，表示最大價(jià)值。

數(shù)據(jù)范圍
0<N,V≤1000
0<vi,wi≤1000

輸入樣例

4 5
1 2
2 4
3 4
4 5

輸出樣例：

8

題目介紹

有 N 件物品和一個(gè)容量為 V的背包，每件物品有各自的價(jià)值且只能被選擇一次，要求在有限的背包容量下，裝入的物品總價(jià)值最大。

「0-1 背包」是較為簡單的動(dòng)態(tài)規(guī)劃問題，也是其余背包問題的基礎(chǔ)。

動(dòng)態(tài)規(guī)劃是不斷決策求最優(yōu)解的過程，「0-1 背包」即是不斷對第 i個(gè)物品的做出決策，「0-1」正好代表不選與選兩種決定

二維

（1）狀態(tài)f[i][j]定義：前 i個(gè)物品，背包容量 j 下的最優(yōu)解（最大價(jià)值）：

當(dāng)前的狀態(tài)依賴于之前的狀態(tài)，可以理解為從初始狀態(tài)f[0][0] = 0開始決策，有 N 件物品，則需要 N 次決策,每一次對第 i 件物品的決策，狀態(tài)f[i][j]不斷由之前的狀態(tài)更新而來。
（2）當(dāng)前背包容量不夠（j < v[i]），沒得選，因此前 i個(gè)物品最優(yōu)解即為前 i−1個(gè)物品最優(yōu)解：

對應(yīng)代碼：f[i][j] = f[i - 1][j]。
（3）當(dāng)前背包容量夠，可以選，因此需要決策選與不選第 i 個(gè)物品：

選：f[i][j] = f[i - 1][j - v[i]] + w[i]。
不選：f[i][j] = f[i - 1][j] 。

我們的決策是如何取到最大價(jià)值，因此以上兩種情況取 max() 。

接下來請看二維求解代碼：

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
int v[MAXN];    // 體積
int w[MAXN];    // 價(jià)值 
int f[MAXN][MAXN];  // f[i][j], j體積下前i個(gè)物品的最大價(jià)值 

int main() 
{
    int n, m;   
    cin >> n >> m;
    for(int i = 1; i <= n; i++) 
        cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= m; j++)
        {
            //  當(dāng)前背包容量裝不進(jìn)第i個(gè)物品，則價(jià)值等于前i-1個(gè)物品
            if(j < v[i]) 
                f[i][j] = f[i - 1][j];
            // 能裝，需進(jìn)行決策是否選擇第i個(gè)物品
            else    
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }           

    cout << f[n][m] << endl;

    return 0;
}

一維

將狀態(tài)f[i][j]優(yōu)化到一維f[j]，實(shí)際上只需要做一個(gè)等價(jià)變形。

原式：f[i][j] = max(f[i-1][j], f[i - 1][j - v[i]] + w[i]);

改成一維：f[j] = max(f[j], f[j - v[i]] + w[i]);

先來看代碼：

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int f[N];
int v[N], w[N];
int n, m;
int main()
{
    

    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) 
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

    cout << f[m] << endl;
}

這中間有一個(gè)點(diǎn)大家可能不太好理解，為什么是for (int j = m; j >= v[i]; j--)，而不是for (int j = v[i]; j <= m; j++)

首先我們先來模擬一下如果是for (int j = v[i]; j <= m; j++)，循環(huán)就是：

for (int i = 1; i <= n; i++) {
        for (int j = v[i]; j <= m; j++) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

來看題

輸入樣例

4 5
1 2
2 4
3 4
4 5
物品      體積     價(jià)值
i=1          1           2
i=2          2           4
i=3          3           4
i=4          4           5 

當(dāng)還沒進(jìn)循環(huán)的時(shí)候

f[0] = 0;  f[1] = 0;  f[2] = 0;  f[3] = 0;  f[4] = 0;  f[5] = 0; 

當(dāng)進(jìn)入循環(huán) i == 1 時(shí)：v[i]=1,w[i]=2;

j=1:f[1]=max(f[1],f[1-1]+2),即max(0,2)=2;即f[1]=2;
j=2:f[2]=max(f[2],f[2-1]+2),即max(0,4)=4;即f[2]=4;
j=3:f[3]=max(f[3],f[3-1]+2),即max(0,6)=6;即f[3]=6;
j=4:f[4]=max(f[4],f[4-1]+2),即max(0,8)=8;即f[4]=8;
j=5:f[5]=max(f[5],f[5-1]+2),即max(0,10)=10;即f[5]=10;

當(dāng)?shù)竭@里的時(shí)候就已經(jīng)出問題了。

//如果 j 層循環(huán)是逆序的： for (int i = 1; i <= n; i++) {<!--{C}%3C!%2D%2D%20%2D%2D%3E--> for (int j = m; j >= v[i]; j--) {<!--{C}%3C!%2D%2D%20%2D%2D%3E--> f[j] = max(f[j], f[j - v[i]] + w[i]); } }//如果 j 層循環(huán)是逆序的：
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

輸入樣例

    4 5
    1 2
    2 4
    3 4
    4 5
    物品      體積   價(jià)值
    i=1          1        2
    i=2          2        4
    i=3          3        4
    i=4          4        5    

    當(dāng)還沒進(jìn)循環(huán)的時(shí)候
    f[0] = 0;  f[1] = 0;  f[2] = 0;  f[3] = 0;  f[4] = 0;  f[5] = 0; 
    當(dāng)進(jìn)入循環(huán)時(shí)i==1，w[i]=2,v[i]=1;
    j=5:f[5]=max(f[5],f[5-1]+2),即max(0,2)=2;即f[5]=2;
    j=4:f[4]=max(f[4],f[4-1]+2),即max(0,2)=2;即f[4]=2;
    j=3:f[3]=max(f[3],f[3-1]+2),即max(0,2)=2;即f[3]=2;
    j=2:f[2]=max(f[2],f[2-1]+2),即max(0,2)=2;即f[2]=2;
    j=1:f[1]=max(f[1],f[1-1]+2),即max(0,2)=2;即f[1]=2;
    當(dāng)進(jìn)入循環(huán) i == 2 時(shí),w[i]=4,v[i]=2;
    j=5:f[5]=max(f[5],f[5-2]+4),即max(2,6)=6,即f[5]=6;
    j=4:f[5]=max(f[4],f[4-2]+4),即max(2,6)=6,即f[4]=6;
    j=3:f[5]=max(f[3],f[3-2]+4),即max(2,6)=6,即f[3]=6;
    j=2:f[5]=max(f[2],f[2-2]+4),即max(2,4)=4,即f[2]=4;
    當(dāng)進(jìn)入循環(huán) i == 3 時(shí): w[i] = 4; v[i] = 3;
    j=5:f[5]=max(f[5],f[5-3]+4),即max(6,8)=8,即f[5]=8;
    j=4:f[4]=max(f[4],f[4-3]+4),即max(6,6)=6,即f[4]=6;
    j=3:f[3]=max(f[3],f[3-3]+4),即max(6,4)=6,即f[3]=6;
    當(dāng)進(jìn)入循環(huán) i == 3 時(shí): w[i] = 5; v[i] = 4;
    j=5:f[5]=max(f[5],f[5-4]+5),即max(8,7)=8,即f[5]=8;
    j=4:f[4]=max(f[4],f[4-4]+5),即max(6,5)=6,即f[4]=6;

模擬結(jié)束，最后max=8：發(fā)現(xiàn)沒有錯(cuò)誤，即逆序就可以解決這個(gè)優(yōu)化的問題了

最后為什么一維情況下枚舉背包容量需要逆序？

在二維情況下，狀態(tài)f[i][j]是由上一輪i - 1的狀態(tài)得來的，f[i][j]與f[i - 1][j]是獨(dú)立的。而優(yōu)化到一維后，如果我們還是正序，則有f[較小體積]更新到f[較大體積]，則有可能本應(yīng)該用第i-1輪的狀態(tài)卻用的是第i輪的狀態(tài)。

簡單來說，一維情況正序更新狀態(tài)f[j]需要用到前面計(jì)算的狀態(tài)已經(jīng)被「污染」，逆序則不會有這樣的問題。

到此這篇關(guān)于C語言數(shù)學(xué)問題與簡單DP背包問題詳解的文章就介紹到這了,更多相關(guān)C語言 數(shù)學(xué)與DP問題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論