时间戳

首页 > 解决方案 > 我的代码有什么问题[Dfs，动态编程]

c++ - 我的代码有什么问题[Dfs，动态编程]

问题描述

我试图用 dfs 和动态编程来解决这个问题。然后我将我的代码提交给我的学校评分员，但答案是错误的。我是否对 dfs 实施了错误。我的代码有什么问题。

PS.对不起我的英语不好

问题 ：

给定一个随机数，你可以用 2 种不同的方式处理这个数字
1.将它除以 3（它必须是可整除的）
2.将它乘以 2

给定n个数字在交换之前找到原始订单
----EXAMPLE1----
INPUT : 6
4 8 6 3 12 9
OUTPUT : 9 3 6 12 4 8
----EXAMPLE2----
INPUT : 4
42 28 84 126
输出：126 42 84 28

这是我的代码

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
int n ;
int input[51];
map<int,int> order ;
map<int,int> memo ;

bool valid(int a){
    for(int i=0;i<n;i++){
        if(input[i]==a)return 1 ;
    }
    return 0 ;
}
void dfs(int st){
    memo[st]=1;
    if(valid(st/3)){
        if(memo[st/3]==0){
            dfs(st/3);
            order[st]+=order[st/3];
        }
        else order[st]+=order[st/3];
    }
    if(valid(st*2)){
        if(memo[st*2]==0){
            dfs(st*2);
            order[st]+=order[st*2];
        }
        else order[st]+=order[st*2];
    }
}

int main(){
    cin >>  n ;
    for(int i=0;i<n;i++){
        cin >> input[i];
        memo[input[i]]=0;
        order[input[i]]=1;
    }
    for(int i=0;i<n;i++){
        if(memo[input[i]]==0)dfs(input[i]);
    }

    for(int i=n;i>=1;i--){
        for(int k=0;k<n;k++){
            if(order[input[k]]==i){
                printf("%d ",input[k]);
                break;
            }
        }
    }
}

我的代码在 10 个测试用例中只给出了 7 个正确答案。我已经问过我的老师，他只告诉我要小心递归。但我无法弄清楚我的递归或其他什么问题

这是一个失败的案例：假设您有序列 3 1 2 4。valid 将为 4 / 3 返回 true，因为它在序列中看到 1。– 微积分高手

#include<bits/stdc++.h>
using namespace std;
struct number{
    long long int r , f3 , f2 ;
};
vector<number> ans ;
bool cmp(number a,number b){
    if(a.f3!=b.f3)return a.f3>=b.f3;
    if(a.f2!=b.f2)return a.f2<=b.f2;
    return true ;
}
int main(){
    int n ;cin>> n ;
    long long int input ;
    
    for(int i=0;i<n;i++){
        cin >> input ;
        long long int r = input ;
        long long int f3 = 0, f2 = 0 ;
        while(input%3==0){
            f3++;
            input/=3;
        }
        while(input%2==0){
            f2++;
            input/=2;
        }
        ans.push_back({r,f3,f2});
    }
    sort(ans.begin(),ans.end(),cmp);

    for(auto i : ans){
        cout << i.r << " " ;
    }
}

标签： c++dynamic-programmingdepth-first-search

解决方案

最黑暗的地方在灯下。

看问题定义：

1.除以3（它必须是整除的）

你在哪里测试可分性？

所以，这里有一个错误：

if(valid(st/3)){

该测试应为：

if(st % 3 == 0 && valid(st/3)){

通过这个简单的改进，所有三个测试用例都通过了。

改进（简化）解决方案的提示

不能被 3 整除的数必须排在能被 3 整除的数之后。同样，那些不能被 9 整除的必须在那些能被 9 整除的之后。同样对于 27、81、...

现在，如果您将您的数字划分为 n = 3^k*m 形式的数字子集，其中 m % 3 != 0，那么在每个这样的子集中，您的算法允许的唯一操作是“乘以 2”。因此，将它们按升序排列就足够了。

这个问题可以不用dfs就可以解决，也不是真的需要递归。只需以一种有趣的方式对数字进行排序：按照数字可被 3 整除的次数降序排列，然后按升序排列。所以，给你一个任务：用一个解决方案挑战你的老师，一旦读入数字，只执行一条指令std::sort（或者qsort，正如我看到你用 C 编写的那样），然后测试解决方案的有效性，并打印出来。

此外，我刚刚证明了如果存在解决方案，它就是唯一的。

推荐阅读