題目描述
如果陣列 A = (a0, a1, · · · , an?1) 滿足以下條件，就說它是一個斐波那契陣列：
-
n ≥ 2；
-
a0 = a1；
-
對于所有的 i(i ≥ 2)，都滿足 ai = ai?1 + ai?2，
現在，給出一個陣列 A ，你可以執行任意次修改，每次修改將陣列中的某個位置的元素修改為一個大于 0 的整數，請問最少修改幾個元素之后，陣列 A 會變成一個斐波那契陣列，
輸入格式
輸入的第一行包含一個整數 n ，表示陣列 A 中的元素個數，
第二行包含 n 個整數 a0, a1, · · · , an?1，相鄰兩個整數之間用一個空格分隔，
輸出格式
輸出一行包含一個整數表示最少需要修改陣列 A 中的幾個元素之后，陣列 A 可以變為一個斐波那契陣列，
樣例輸入
3
4 6 9
樣例輸出
4
解答
- 這道題是典型的斐波那契數列題，而且因為題目的資料范圍很大，使用暴力遞回幾乎全部資料都會超時，所以我們使用動態規劃進行解答
- 寫出基本的解答斐波那契數列的動態規劃代碼，后續對此進行更改
dp[1] = dp[2] = 1;
for (int i = 3; ; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
- 因為輸入的資料會出現不以1，1，2...開頭的資料，而是2，2，4，6 ....等等，我們不能只計算以1開始的斐波那契數列，所以我們暴力遍歷1-1000000開始的所有數列，并以修改次數最小的那次遍歷作為答案，所以我們可以定義函式int dp(int start)，回傳以start開始的數列與原陣列需要修改的次數
public static int dp(int start) {
// range代表dp陣列的范圍，因為dp陣列大小只有100，遍歷arr陣列會超過dp陣列的范圍
int range = 2;
dp[1] = dp[2] = start;
for (int i = 3; ; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
// 資料范圍在1000000以內
if (dp[i] > 1000000) break;
range++;
}
int ans = 0;
for (int i = 1; i <= range; i++) {
if (arr[i] == dp[i]) {
ans++;
}
}
return n - ans;
}
- 暴力遍歷，答案為每一個數字開始的陣列中修改最少次數的那一次
int ans = Integer.MAX_VALUE;
for (int i = 1; i <= 1000000; i++) {
int cur = dp(i);
ans = Integer.min(cur, ans);
}
System.out.println(ans);
- 需要注意一點，就是我為什么會暴力遍歷1-1000000 的dp數列，因為求斐波那契數列的程序非常快，然后剪枝掉超過資料范圍的回圈，因為以1開始的斐波那契數列在31項時就會超過1000000，那么每次遍歷不會回圈2（31）次，所以可以暴力解此題
完整代碼
package lanqiao.java13cFinal;
import java.util.Scanner;
public class E {
static int N = 100005;
static int n;
static int[] arr = new int[N];
static int[] dp = new int[100];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 1; i <= n; i++) {
arr[i] = sc.nextInt();
}
int ans = Integer.MAX_VALUE;
for (int i = 1; i <= 1000000; i++) {
int cur = dp(i);
ans = Integer.min(cur, ans);
}
System.out.println(ans);
}
public static int dp(int start) {
int range = 2;
dp[1] = dp[2] = start;
for (int i = 3; ; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
if (dp[i] > 1000000) break;
range++;
}
int ans = 0;
for (int i = 1; i <= range; i++) {
if (arr[i] == dp[i]) {
ans++;
}
}
return n - ans;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/553235.html
標籤：其他
下一篇：返回列表