จำนวนเซ็กเมนต์สูงสุดของความยาว a, b และ c ใน C++

ภารกิจคือการหาจำนวนสูงสุดของส่วนของเส้นตรงที่มีความยาว a, b และ c ที่สามารถเกิดขึ้นได้จากจำนวนเต็มบวกที่กำหนด N

ตอนนี้มาทำความเข้าใจสิ่งที่เราต้องทำโดยใช้ตัวอย่าง -

ป้อนข้อมูล − N=8, a=3, b=1, c=2

ผลลัพธ์ − 8

คำอธิบาย − N สามารถแบ่งออกเป็น 8 เซ็กเมนต์ของ b ซึ่งเป็นจำนวนเซ็กเมนต์สูงสุดที่สามารถทำได้

ป้อนข้อมูล − N=13, a=2, b=7, c=3

ผลผลิต − 6

แนวทางที่ใช้ในโปรแกรมด้านล่างดังนี้

• ในฟังก์ชัน MaxSegment() ให้ประกาศอาร์เรย์ MaxSeg[N +1] ประเภท int และเริ่มต้นด้วยค่า -1

• ใส่ดัชนีที่ศูนย์เท่ากับ 0 เนื่องจากจะไม่มีส่วนใดส่วนหนึ่ง

• วนจาก i=0 ถึง i

• ภายในคำสั่ง if ด้านบน ใส่คำสั่งอื่น if(i + a <=N) และ putMaxSeg[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