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

PHPz
Lepaskan: 2023-08-29 22:25:03
ke hadapan
719 orang telah melayarinya

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
Salin selepas log masuk

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";
}
Salin selepas log masuk

Output

252
Salin selepas log masuk

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!

Label berkaitan:
sumber:tutorialspoint.com
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan