Penggunaan fungsi rekursif C++ dalam algoritma pengaturcaraan dinamik?

Penggunaan fungsi rekursif dalam algoritma pengaturcaraan dinamik boleh menyelesaikan masalah pengoptimuman dengan berkesan. Contohnya ialah penyelesai jujukan Fibonacci, fungsi rekursif berdasarkan formula F(n) = F(n-1) + F(n-2). Fungsi rekursif boleh dioptimumkan dengan menggunakan teknik memoisasi untuk menyimpan penyelesaian submasalah dan mengelakkan pengiraan berganda. Contoh teknik memo adalah untuk mencipta tatasusunan dan memulakan nilai pertama kepada 1. Dengan lelaran gelung, jika nilai semasa memo[i] dalam memo ialah 0, ini bermakna submasalah itu belum dikira lagi, jadi fungsi akan memanggil dirinya secara rekursif untuk mengira dan menyimpannya dalam memo. Akhirnya, nombor Fibonacci ke-n dalam memo dikembalikan.

Aplikasi fungsi rekursif C++ dalam algoritma pengaturcaraan dinamik

Pengaturcaraan dinamik ialah algoritma yang digunakan untuk menyelesaikan masalah pengoptimuman. Ia bergantung pada memecahkan masalah kepada sub-masalah yang lebih kecil dan menyimpan penyelesaian untuk setiap sub-masalah untuk mengelakkan pengiraan berganda. Fungsi rekursif memainkan peranan penting dalam pengaturcaraan dinamik kerana ia membolehkan kami menguraikan masalah dengan berkesan dengan memanggil fungsi yang sama berulang kali.

Berikut ialah contoh fungsi rekursif yang menyelesaikan jujukan Fibonacci yang dilaksanakan dalam C++:

int fibonacci(int n) {
  if (n == 0 || n == 1) {
    return 1;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

Fungsi rekursif ini berdasarkan formula jujukan Fibonacci berikut:

F(n) = F(n-1) + F(n-2)

di mana F(n) ialah nombor ke-n jujukan Fibonacci.

Dalam kaedah pengaturcaraan dinamik, kami boleh mengoptimumkan fungsi rekursif dengan menyimpan penyelesaian sub-masalah yang dikira. Ini boleh dicapai dengan menggunakan teknik memoisasi, di mana penyelesaian kepada setiap submasalah disimpan dalam struktur data (seperti tatasusunan atau kamus) selepas pengiraan pertama.

Sebagai contoh, berikut ialah fungsi pengaturcaraan dinamik untuk menyelesaikan jujukan Fibonacci dengan memo yang dilaksanakan dalam C++:

int fibonacci_dp(int n) {
  // 初始化备忘录，大小为 n+1，因为斐波那契数列从 0 开始
  int memo[n + 1];
  
  // 初始化备忘录中第一个值为 1
  memo[0] = 1;
  
  for (int i = 1; i <= n; ++i) {
    if (memo[i] == 0) {
      memo[i] = fibonacci_dp(i - 1) + fibonacci_dp(i - 2);
    }
  }
  return memo[n];
}

Fungsi pengaturcaraan dinamik ini mengelakkan pengiraan submasalah berulang dengan menggunakan memo. Ia mula-mula mencipta tatasusunan memo saiz n+1 dan memulakan nilai pertama kepada 1. Ia kemudian menggunakan gelung for untuk mengulangi semua nilai dari 1 hingga n. Jika nilai semasa memo[i] dalam memo ialah 0, ini bermakna submasalah itu belum dikira lagi, jadi fungsi akan secara rekursif memanggil dirinya sendiri untuk mengira dan menyimpannya dalam memo. Akhirnya, ia mengembalikan nombor Fibonacci ke-1 dalam memo.

Fungsi rekursif dalam algoritma pengaturcaraan dinamik ialah alat yang berkuasa untuk menyelesaikan masalah pengoptimuman dan mengurangkan masa pengiraan. Dengan menggabungkan teknik memoisasi dengan fungsi rekursif, kami boleh meningkatkan kecekapan algoritma dengan ketara, terutamanya apabila menyelesaikan masalah berskala besar.

Atas ialah kandungan terperinci Penggunaan fungsi rekursif C++ dalam algoritma pengaturcaraan dinamik?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!