資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中長度為a、b和c的線段最大數量
給定任務是從給定的正整數N中找到可以形成的長度為a、b和c的線段的最大數量。
讓我們用一個例子來理解我們必須做什麼：
輸入 - N=8，a=3，b=1，c=2
輸出 - 8
解釋 - N可以分成8個長度為b的線段，這是可以形成的最大線段數。
輸入 - N=13，a=2，b=7，c=3
輸出 - 6
下面程式中使用的演算法如下：
在MaxSegment()函式中，宣告一個型別為int的陣列MaxSeg[N+1]，並將其初始化為-1。
將第零個索引設定為0，因為它沒有線段。
迴圈從i=0到i
在上面的if語句內，再新增一個語句if(i + a <=N)，並設定MaxSeg[i + a] = max(MaxSeg[i] + 1, MaxSeg[i + a]);
對b和c重複上述步驟。
迴圈結束後，返回MaxSeg[N]。
示例
#include <bits/stdc++.h>
using namespace std;
int MaxSegment(int N, int a,int b, int c){
/* It will store the maximum number of segments each index can have*/
int MaxSeg[N + 1];
// initialization
memset(MaxSeg, -1, sizeof(MaxSeg));
// 0th index will have 0 segments
MaxSeg[0] = 0;
// traversing for every segments till n
for (int i = 0; i < N; i++){
if (MaxSeg[i] != -1){
if(i + a <= N ){
MaxSeg[i + a] = max(MaxSeg[i] + 1, MaxSeg[i + a]);
}
if(i + b <= N ){
MaxSeg[i + b] = max(MaxSeg[i] + 1, MaxSeg[i + b]);
}
if(i + c <= N ){
MaxSeg[i + c] = max(MaxSeg[i] + 1, MaxSeg[i + c]);
}
}
}
return MaxSeg[N];
}
int main(){
int N = 13, a = 2, b = 7, c = 3;
cout << MaxSegment(N, a, b, c);
return 0;
}輸出
如果我們執行上面的程式碼，我們將得到以下輸出：
6
更新於：2020年8月17日
191 次瀏覽
廣告