home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

โปรแกรมเรียกซ้ำพิมพ์สูตร GCD ของ n จำนวนเต็มใน C++

ภาพรวม

ได้รับจำนวนเต็มเป็นอินพุต เป้าหมายคือพิมพ์สูตร (Formula) ของ GCD ของ n จำนวนโดยใช้การเรียกซ้ำ (Recursion)

เราทราบว่า GCD ของสามจำนวน a1, b1, c1 คือ gcd(a1, gcd(b1, c1)) เช่นเดียวกันสำหรับมากกว่าสามจำนวน สูตรคือ gcd(a1, gcd(b1, gcd(c1... gcd(y1, z1))))

ตัวอย่าง

อินพุต − Num = 4

เอาต์พุต − Formula is:

GCD(int a3, GCD(int a2, GCD(int a1, int b1)))

อินพุต − Num = 6

เอาต์พุต − Formula is: GCD(int a5, GCD(int a4, GCD(int a3, GCD(int a2, GCD(int a1, int b1)))))

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

ใช้ฟังก์ชันเรียกซ้ำ gcdFormula(int num1) รับจำนวนตัวเลข คืนสตริงที่เป็นสูตร GCD

Base case: หาก num1 == 1 คืนสตริง "int b" + to_string(num1)

Recursive case: พิมพ์ "GCD(int a" + (num1-1) + ", " แล้วเรียกซ้ำ gcdFormula(num1-1) และต่อท้าย ")"

  • รับตัวเลข Num
  • ฟังก์ชัน gcdFormula(int num1) คืนสตริงสูตร GCD
  • หาก num1 == 1 คืน "int b" + to_string(num1)
  • มิฉะนั้น พิมพ์ "GCD(int a" << num1-1 << ", " แล้วคืน gcdFormula(num1-1) + ")"
  • พิมพ์ผลลัพธ์ใน main

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

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

string gcdFormula(int num1){ 
    if (num1 == 1){ 
        return ("int b" + to_string(num1)); 
    } else { 
        cout << "GCD(int a" << num1-1 << ", "; 
        return (gcdFormula(num1 - 1) + ")"); 
    } 
} 

int main(){ 
    int Num = 6; 
    cout << "Formula is :" << endl; 
    cout << gcdFormula(Num); 
    return 0; 
}

ผลลัพธ์

Formula is: GCD(int a6, GCD(int a5, GCD(int a4, GCD(int a3, GCD(int a2, GCD(int a1, int b1))))))