จำนวนชุดขั้นต่ำที่มีตัวเลขน้อยกว่า Y ใน C++

คำชี้แจงปัญหา

ให้ชุดตัวเลขต่อเนื่องกันและตัวเลข Y ภารกิจคือการค้นหาจำนวนชุดขั้นต่ำเพื่อให้ทุกชุดเป็นไปตามกฎด้านล่าง -

• ชุดควรมีตัวเลขต่อเนื่องกัน
• ไม่สามารถใช้ตัวเลขได้มากกว่าหนึ่งครั้ง
• ตัวเลขในชุดไม่ควรเกิน Y

ตัวอย่าง

หาก str =“1234” และ Y =20 คำตอบคือ 3 ตามชุดด้านล่างจะถูกสร้างขึ้น –

{12} {3} และ {4}

อัลกอริทึม

• แปลงสตริงเป็นตัวเลข
• ถ้าตัวเลขไม่มากกว่า Y ให้ทำเครื่องหมาย f =1
• หากตัวเลขเกิน Y ให้เพิ่มจำนวนถ้า f =1 และกำหนดค่าเริ่มต้น f ใหม่เป็น 0 และกำหนดค่าเริ่มต้น num เป็น s[i]-'0' หรือ num เป็น 0
• หลังจากวนซ้ำในสตริงแล้ว ให้เพิ่มจำนวนถ้า f เป็น 1

ตัวอย่าง

#include <iostream>
#include <string>
using namespace std;
int getMinSets(string str, int y) {
   int cnt = 0;
   int num = 0;
   int l = str.length();
   int f = 0;
   for (int i = 0; i < l; ++i) {
      num = num * 10 + str[i] - 48;
      if (num <= y) {
         f = 1;
         continue;
      }
      if (f) {
         ++cnt;
      }
      num = str[i] - '0';
      f = 0;
      if (num <= y) {
         f = 1;
      } else {
         num = 0;
      }
   }
   if (f) {
      ++cnt;
   }
   return cnt;
}
int main() {
   string str = "1234";
   int y = 20;
   cout << "Minimum sets = " << getMinSets(str, y) << endl;
   return 0;
}

ผลลัพธ์

เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -

Minimum sets = 3