กำหนดจำนวนเต็มเป็นอินพุต เป้าหมายคือการหาจำนวนขั้นตอนขั้นต่ำหรือการดำเนินการที่จำเป็นในการลดจำนวนอินพุตเป็น 1 การดำเนินการที่สามารถทำได้จะเป็น:
-
ถ้าจำนวนเป็นเลขคู่ ให้หารด้วย 2
-
หาก Number เป็นเลขคี่ ให้เพิ่มหรือลดทีละ 1
ตัวอย่าง
ป้อนข้อมูล − Number=28
ผลผลิต − ขั้นตอนขั้นต่ำเพื่อลด 28 เป็น 1:6
คำอธิบาย −
28 เป็นคู่ - หารด้วย 2 =14
14 เป็นคู่ - หารด้วย 2 =7
7 เป็นเลขคี่ - เพิ่มขึ้น 1 =8
8 เป็นคู่ - หารด้วย 2 =4
4 เป็นคู่ - หารด้วย 2 =2
2 เป็นคู่ - หารด้วย 2 =1
ป้อนข้อมูล − Number=9
ผลผลิต - ขั้นตอนขั้นต่ำเพื่อลด 9 เป็น 1:4
คำอธิบาย −
9 เป็นเลขคี่ - ลดลง 1 =8
8 เป็นคู่ - หารด้วย 2 =4
4 เป็นคู่ - หารด้วย 2 =2
2 เป็นคู่ - หารด้วย 2 =1
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
ในวิธีนี้ใช้วิธีการแบบเรียกซ้ำเพื่อตรวจสอบการดำเนินการขั้นต่ำที่จำเป็นในการลดจำนวนเป็น 1 ในกรณีที่หารด้วย 2 ง่ายๆ ให้ตรวจสอบแบบเรียกซ้ำสำหรับวิธีขั้นต่ำสำหรับ Number+1 หรือ Number-1 แล้วแต่จำนวนใดจะน้อยกว่า
-
นำตัวเลขเข้าเป็นจำนวนเต็ม
-
ฟังก์ชัน minWays(int num) รับ num เป็นอินพุตและส่งกลับจำนวนการดำเนินการขั้นต่ำที่จำเป็นในการลด num เป็น 1
-
นำตัวแปร tmp1, tmp2 และ min เป็นจำนวนเต็ม
-
ถ้า num เป็น 0 ให้คืนค่า 1
-
หาก num%2==0 จะเป็นคู่ ให้ตั้งค่า num=num/2
-
หาก num เป็นเลขคี่ ให้ตั้งค่า tmp1=minWays(num-1) และ tmp2=minWays(num+1)
-
ตั้งค่าขั้นต่ำเป็นขั้นต่ำของ tmp1 และ tmp2
-
กลับ 1+นาที
-
ในตอนท้ายเราจะได้ผลลัพธ์ที่ต้องการ
-
พิมพ์ผลในหลัก
ตัวอย่าง
#include <iostream>
using namespace std;
int minWays(int num){
int tmp1,tmp2,min;
if (num == 1){
return 0;
}
else if (num % 2 == 0){
tmp1=minWays(num/2);
return (1 + tmp1);
}
else{
int tmp1=minWays(num - 1);
int tmp2=minWays(num + 1);
int min=tmp1<tmp2?tmp1:tmp2;
return (1 + min);
}
}
int main(){
int Number = 21;
cout <<"Minimum steps to reduce "<<Number<<" to 1: "<<minWays(Number);
return 0;
} ผลลัพธ์
หากเรารันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้
Minimum steps to reduce 21 to 1: 6
