Pengaturcaraan dalam C++, cari bilangan laluan dari satu titik ke titik lain dalam grid

Dalam artikel ini, kita diberi masalah di mana kita perlu mencari jumlah laluan dari titik A ke titik B, di mana A dan B adalah titik tetap, iaitu A ialah titik sudut kiri atas dalam grid dan B ialah titik sudut kanan bawah dalam grid, contohnya −

Input : N = 5
Output : 252

Input : N = 4
Output : 70

Input : N = 3
Output : 20

Dalam masalah yang diberikan, kita boleh merumuskan jawapan dengan pemerhatian mudah dan dapatkan Dapatkan keputusan.

Kaedah mencari penyelesaian

Dalam kaedah ini kita memperoleh formula dengan memerhati bahawa apabila melintasi grid dari A ke B, kita perlu pergi ke kanan Perjalanan n kali dan turun ke bawah n kali, yang bermaksud kita perlu mencari semua kemungkinan kombinasi laluan, jadi kita mendapat formula gabungan (n+n) dan n.

Contoh

#include<bits/stdc++.h>

using namespace std;
int fact(int n){ // factorial function 
   if(n <= 1)
      return 1;
   return n * fact(n-1);
}
int main() {
   int n = 5; // given n
   int answer = 0; // our answer
   answer = fact(n+n); // finding factorial of 2*n
   answer = answer / (fact(n) * fact(n)); // (2*n)! / (n! + n!)
   cout << answer << "\n";
}

Output

252

Penjelasan kod di atas

#🎜2 dalam kod ini, kita# dalam kod ini formula gabungan dari n ke n, kerana kita tahu bahawa dari titik A ke titik B, kita memerlukan tepat 2*n operasi dalam dua arah, iaitu, terdapat n operasi dalam satu arah dan n operasi dalam arah yang lain semua kemungkinan gabungan operasi ini, iaitu (2*n)!/ (n! + n!). Kerumitan masa keseluruhan program yang diberikan ialah O(1), yang bermaksud bahawa kerumitan kami tidak bergantung pada n yang diberikan.

Kesimpulan

Dalam artikel ini, kami membincangkan masalah untuk mencari bilangan laluan dari satu titik ke titik lain dalam grid. Kami juga mempelajari program C++ untuk masalah ini dan pendekatan lengkap kami untuk menyelesaikannya. Kita boleh menulis program yang sama dalam bahasa lain seperti C, java, python dan bahasa lain. Kami berharap artikel ini dapat membantu anda.

Atas ialah kandungan terperinci Pengaturcaraan dalam C++, cari bilangan laluan dari satu titik ke titik lain dalam grid. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!