เราได้รับหมายเลข N เป้าหมายคือการนับจำนวนขั้นตอนที่จำเป็นในการลดจำนวนเป็น 1 โดยทำตามกฎ –
-
หากตัวเลขเป็นเลขยกกำลัง 2 ให้ย่อเป็นครึ่งหนึ่ง
-
อย่างอื่นลดเป็น N- (กำลังใกล้ที่สุดของ 2 ซึ่งน้อยกว่า N)
สำหรับขั้นตอนที่ 1 เราจะตรวจสอบว่า N เป็นกำลัง 2 หรือไม่ โดยตรวจสอบว่า ceil(log2(N)), floor(log2(N)) ส่งคืนผลลัพธ์เดียวกันหรือไม่ ถ้าใช่ ก็ N=N/3 นับการทำงานที่เพิ่มขึ้น
หากผลลัพธ์ของขั้นตอนที่ 1 เป็นเท็จ เราจะดำเนินการขั้นตอนที่ 2 และลบกำลัง 2 ที่น้อยกว่า N ที่ใกล้ที่สุดออกจาก N ยกกำลังที่ใกล้เคียงที่สุดที่ 2 น้อยกว่า N จะถูกคำนวณเป็น −
x=floor(log2(N)) → เมื่อ N ไม่ใช่กำลังของ 2 log2(N) จะให้ค่าทศนิยม โดย floor จะลดจำนวนลงเป็นจำนวนเต็มที่ใกล้เคียงที่สุดที่น้อยกว่า N
ตอนนี้ N=N-pow(2,x) → pow(2,x) จะให้กำลังที่ใกล้เคียงที่สุดที่ 2 น้อยกว่า N ลด N.
มาทำความเข้าใจกับตัวอย่างกัน
ป้อนข้อมูล − N=20
ผลผลิต -:จำนวนขั้นตอนที่ต้องการ − 3
คำอธิบาย − N=20
20 is not power of 2. Step 2. Reduce nearest power of 2 less than N from N. N=20- 16=4. Count=1. 4 is power of 2. Step 1. Reduce N to its half. N=4/2=2. Count=2. 2 is power of 2. Step 1. Reduce N to its half. N=2/2=1. Count=3. N is 1 total step count=3.
ป้อนข้อมูล − N=32
ผลผลิต จำนวนขั้นตอนที่ต้องการ − 5
คำอธิบาย − N=32
32 is power of 2. Step 1. Reduce N to its half. N=32/2=16. Count=1. 16 is power of 2. Step 1. Reduce N to its half. N=16/2=8. Count=2. 8 is power of 2. Step 1. Reduce N to its half. N=8/2=4. Count=3. 4 is power of 2. Step 1. Reduce N to its half. N=4/2=2. Count=4. 2 is power of 2. Step 1. Reduce N to its half. N=2/2=1. Count=5. N is 1 total step count=5.
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
เราใช้จำนวนเต็ม N เพื่อเก็บค่าจำนวนเต็ม
-
ฟังก์ชัน stepCount(int n) รับ N และส่งกลับจำนวนขั้นตอนที่จำเป็นเพื่อลดเป็น 1
-
นับขั้นตอนเริ่มต้นเป็น 0
-
ตอนนี้ while(n!=1) ทำทั้งสองขั้นตอนที่ 1 และ 2 ตามค่าของ n
-
ถ้า n เป็นกำลังของ 2 ( ceil(log2(n))==floor(log2(n)) จะเป็น true ) ให้ลด n ลงครึ่งหนึ่ง จำนวนที่เพิ่มขึ้น
-
ถ้าไม่ใช่กำลัง 2 ให้ลด n โดย pow(2,x) โดยที่ x คือ floor(log2(n)) จำนวนที่เพิ่มขึ้น
-
เมื่อการวนซ้ำสิ้นสุดลง การนับจะมีจำนวนการดำเนินการที่ดำเนินการ
-
ผลตอบแทนนับตามผลลัพธ์ที่ต้องการ
ตัวอย่าง
#include <iostream>
#include <math.h>
using namespace std;
// Function to return number of steps for reduction
int stepCount(int n){
int count=0;
while(n!=1){
if(ceil(log2(n))==floor(log2(n))) //if n is power of 2 then this is true{
n=n/2; //reduce n to half
count++;
} else {
int x=floor(log2(n)); //floor value
n=n-(pow(2,x)); //2^x is nearest power of 2 which is less than n
count++;
}
}
return count;
}
int main(){
int N = 96;
cout <<"Count of steps required to reduce N to 1:"<<stepCount(N);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Count of steps required to reduce N to 1:6
