回溯 + 美妙的剪枝_P1625

User_test

TA的个人主页 >

文章

粉丝

126

获赞

访问

8.6k

回溯 + 美妙的剪枝

User_test

P1625 上海交通大学2017年机试题

发布于2022年3月5日 21:40

阅读数 8.6k

package 上海交通大学历年机试真题;

import java.util.Scanner;
//回溯算法加美丽的剪枝已AC
public class Q_2017_problemC {
   int count = 0;
   public int sum_of_fibonacci(int num) {
       int fib[] = new int[39];//这个数组用来记录所有小于100000000的Fibonacci的数
       int prev = 1,now=1;
       int temp = 0;
       fib[0] = 1;
       for(int i = 1;i < 39;i++) {
           temp = now;
           now = now + prev;
           prev = temp;
           fib[i] = now;
     &...

登录查看完整内容

登录后发布评论

4 条评论

a964208170

2023年6月24日 19:43

贴个代码：

import java.util.Scanner;

public class Main {
    static final int[] fib = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155};
    int ans = 0;

    public void backTrack(int n, long curSum, boolean[] visited, int pos) {
        if (curSum >= n || pos < 0) {
            if (curSum == n) ans++;
            return;
        }

        for (int i = pos; i >= 0; i--) {
            if (!visited[i]) {
                if (i + 2 < fib.length && curSum + fib[i + 2] - 2 < n) break;
                visited[i] = true;
                backTrack(n, curSum + fib[i], visited, i);
                visited[i] = false;
            }
        }
    }

    public int sumOfFibonacci(int n) {
        backTrack(n, 0, new boolean[fib.length], fib.length - 1);
        System.out.println(ans);
        return ans;
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int n = sc.nextInt();
            new Main().sumOfFibonacci(n);
        }
    }
}

a964208170

2023年6月24日 19:41

其实可以再优化，now_index_max_sum[i] = fib[i + 2] - 2，注意到这个规律就可以省去对求和的计算。

User_test

2022年3月5日 21:41

图片地址：https://wx4.sinaimg.cn/orj360/0075qSNugy1gzzc27oi1cj32tc240kjl.jpg

User_test : 回复 User_test：也可以直接搜微博名看图片主要这里没法上传高清图

2022年3月5日 21:42