ลดตัวเลขให้เหลือ 1 ด้วยการดำเนินการที่กำหนดใน C++

ภาพรวม

ได้รับจำนวนเต็ม Number เป็นอินพุต เป้าหมายคือหาจำนวนขั้นตอน (Operations) น้อยที่สุดที่ต้องใช้เพื่อลด Number ให้เหลือ 1 การดำเนินการที่อนุญาต:

• หาก Number เป็นเลขคู่ ให้หารด้วย 2
• หาก Number เป็นเลขคี่ ให้บวก 1 หรือลบ 1

ตัวอย่าง

อินพุต − Number = 28

เอาต์พุต − Minimum steps to reduce 28 to 1: 6

คำอธิบาย −

28 คู่ หาร 2 = 14

14 คู่ หาร 2 = 7

7 คี่ บวก 1 = 8

8 คู่ หาร 2 = 4

4 คู่ หาร 2 = 2

2 คู่ หาร 2 = 1

อินพุต − Number = 9

เอาต์พุต − Minimum steps to reduce 9 to 1: 4

คำอธิบาย −

9 คี่ ลบ 1 = 8

8 คู่ หาร 2 = 4

4 คู่ หาร 2 = 2

2 คู่ หาร 2 = 1

แนวทางการแก้ปัญหา

ใช้การเรียกซ้ำตรวจสอบจำนวนการดำเนินการน้อยที่สุด หากเลขคู่ หาร 2 ทันที หากเลขคี่ เรียกซ้ำหาทางที่น้อยที่สุดระหว่าง Number+1 และ Number-1

• รับตัวเลขอินพุต Number
• ฟังก์ชัน minWays(int num) คืนจำนวนขั้นตอนน้อยที่สุด
• ตัวแปร tmp1, tmp2, min
• หาก num == 1 คืน 0
• หาก num%2==0 (คู่) เรียก minWays(num/2) คืน 1 + ผลลัพธ์
• หากคี่ เรียก minWays(num-1) และ minWays(num+1) หาค่าน้อยที่สุด คืน 1 + min
• พิมพ์ผลลัพธ์ใน main

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

#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 { 
        tmp1 = minWays(num - 1); 
        tmp2 = minWays(num + 1); 
        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