เรามีให้สามตัวเลข X, Y และ N ( เพื่อกำหนดช่วง [1,N] ) เป้าหมายคือการหาตัวเลขทั้งหมดในช่วง [1,N] ที่สร้างได้โดยใช้ X และ Y กี่ครั้งก็ได้..
ตัวอย่างเช่น ถ้า X=2 และ Y=3 หมายเลข 6 สามารถสร้างได้โดยใช้ 2 สามครั้ง ( 2+2+2 ) หรือ 3 สองครั้ง ( 3+3 ) ในทำนองเดียวกัน 7 สามารถสร้างได้โดยใช้ 2 ครั้งและ 3 ครั้ง ( 2+2+3 )
เราจะทำสิ่งนี้โดยลบ X หรือ Y จากตัวเลขแต่ละตัวจาก 1 ถึง N หากจำนวนสุดท้ายลดลงเหลือ 0 ให้นับการเพิ่มขึ้น
มาทำความเข้าใจกับตัวอย่างกัน
ป้อนข้อมูล
N=10 X=4, Y=3
ผลผลิต
Total numbers constructed using X & Y only: 7
คำอธิบาย
Numbers constructed by 3 and 4 only: 3, 4, 6 (3+3), 7 (3+4), 8 (4+4), 9 (3+3+3), 10 (3+3+4)
ป้อนข้อมูล
N=10 X=5, Y=4
ผลผลิต
Total numbers constructed using X & Y only: 5
คำอธิบาย
Numbers constructed by 4 and 5 only: 4, 5, 8(4+4), 9 (4+5), 10 (5+5)
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
เราใช้จำนวนเต็มสามจำนวน X, Y และ N
-
ฟังก์ชัน constructNums(int n,int x,int y) คืนค่าจำนวนตัวเลขที่สามารถสร้างได้โดยใช้ x และ y เท่านั้น
-
ใช้ตัวแปรเริ่มต้นนับเป็น 0 สำหรับตัวเลขดังกล่าว
-
ข้ามช่วงของตัวเลขโดยใช้การวนซ้ำ i=1 ถึง i<=n
-
ตอนนี้สำหรับแต่ละตัวเลข num=i โดยใช้ while loop ตรวจสอบว่า num>0,
-
while(num%x==0) และ num ไม่ใช่ 0 ลบ x ออกจากมัน
-
while(num%y==0) และ num ไม่ใช่ 0 ลบ y ออกจากมัน
-
หากหลังจากลบจำนวน x และ y แล้ว หารด้วยทั้งคู่ไม่ลงตัวและมากกว่าทั้งคู่ ให้ลบทั้ง x และ y ออกจากมัน
-
ถ้าหลังจากวนรอบนอก ให้ตรวจสอบว่า num เป็น 0 หรือไม่ หมายถึง x, y หรือทั้งสองอย่างสามารถสร้าง num ได้ จำนวนที่เพิ่มขึ้น
-
เมื่อสิ้นสุดการวนซ้ำทั้งหมดจะมีจำนวนรวม
-
คืนค่าการนับเป็นผลลัพธ์
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int constructNums(int n,int x,int y){
int count = 0;
for (int i = 1; i <= n; i++) {
int num = i;
while(num>0){
while((num%x)==0 && num!=0)
num-=x;
while((num%y)==0 && num!=0)
num-=y;
if (num>x && num>y)
num=num-x-y;
else
break;
}
if (num==0)
{ count++;}
}
return count;
}
int main(){
int N=20;
int X=5,Y=4;
cout <<"Total numbers constructed using X & Y only:"<<constructNums(N,X,Y);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Total numbers constructed using X & Y only:14
