นับจำนวนการดำเนินการลด N ให้เหลือ 0 ใน C++

เราได้รับจำนวนเต็มบวก N เป้าหมายคือหาจำนวนการดำเนินการที่ต้องใช้เพื่อลด N ให้เหลือ 0 การดำเนินการที่ใช้คือ N=N-P โดย P คือตัวหารเฉพาะน้อยที่สุดของ P

มาดูตัวอย่าง

อินพุต − N=17

เอาต์พุต − จำนวนการดำเนินการลด N ให้เหลือ 0 คือ 1

คำอธิบาย − ตัวหารเฉพาะน้อยที่สุดของ 17 คือ 17 เอง ดังนั้นการดำเนินการใช้เพียงครั้งเดียว 17-17=0

อินพุต − N=20

เอาต์พุต − จำนวนการดำเนินการลด N ให้เหลือ 0 คือ 10

คำอธิบาย − ตัวหารเฉพาะน้อยที่สุดของ 20 คือ 2 ลบ 2 ซ้ำๆ และหาตัวหารเฉพาะถัดไป:

20%2==0, 20-2=18
18%2==0, 18-2=16 …………… 14, 12, 10, 8, 6, 4, 2, 0
รวม 10 ครั้งที่การดำเนินการถูกใช้

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

สำหรับ N คู่ทั้งหมด ตัวหารเฉพาะน้อยที่สุดจะเป็น 2 เสมอ และการลบ 2 จาก N คู่จะได้จำนวนคู่อีกครั้ง สำหรับจำนวนคี่ ตัวหารเฉพาะน้อยที่สุดจะเป็นคี่ หลังจากลบคี่จากคี่ จำนวนจะกลายเป็นคู่ ดังนั้น 2 จะกลายเป็นตัวหารเฉพาะน้อยที่สุดอีกครั้ง เพื่อหาตัวหารเฉพาะน้อยที่สุด เริ่มจาก i=2 ถึง i*i<N และ N%i==0 จำนวนการดำเนินการทั้งหมดจะเป็น count=1 + (N-i)/2

• รับจำนวนเต็ม N เป็นอินพุต
• ฟังก์ชัน N_to_Zero(int N) รับ N คืนจำนวนการดำเนินการลด N ให้เหลือ 0
• กำหนดค่าเริ่มต้นของ count เป็น 0
• เริ่มจาก i=2 เดินทางด้วยลูป while (i*i)<N && (N%i!=0) เพิ่ม i
• ถ้า (i*i) เกิน N กำหนด i=N
• จำนวนการดำเนินการจะเป็น 1+(N-i)/2
• กำหนด count เป็น 1+(N-i)/2
• คืน count

ตัวอย่างโค้ด C++

#include<bits/stdc++.h>
using namespace std;

int N_to_Zero(int N){
    int count = 0;
    int i = 2;
    while((i * i) < N && (N % i)){
        i++;
    }
    if((i * i) > N){
        i = N;
    }
    count = 1 + (N-i)/2;
    return count;
}

int main(){
    int N = 10;
    cout<<"Count of operations of the given type required to reduce N to 0 are: "<<N_to_Zero(N);
    return 0;
}

เอาต์พุต

หากรันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −

Count of operations of the given type required to reduce N to 0 are: 5