我的代码有什么问题 [Dfs，动态规划]

Question

我尝试用 dfs 和动态规划来解决这个问题。然后我将我的代码提交给我的学校评分员，但答案是错误的。我是不是用 dfs 实现了一些错误。我的代码有什么问题。

PS.sorry 因为我的英语不好

The problem :

given a random number there's 2 different way you can do with this number
1.divide it by 3 (it has to be divisible)
2.multiply it by 2

given n number find the original order before it was swapped
----EXAMPLE1----
INPUT : 6
4 8 6 3 12 9
OUTPUT : 9 3 6 12 4 8
----EXAMPLE2----
INPUT : 4
42 28 84 126
OUTPUT : 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;
            }
        }
    }
}

OP 应该首先告诉我们的信息:

my code gave the correct answer only 7 of 10 test case .i've already asked my teacher he only told me to be careful with the recursion . but i couldn't figure it out what's wrong with my recursion or something else

一个“失败”的例子：

Here's a failing case: Say you have the sequence 3 1 2 4. valid will return true for 4 / 3 because it sees 1 in the sequence. – Calculuswhiz

更好的解决方案

#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 << " " ;
    }
}

Answer 1

最暗的地方在lamp下面。

看问题定义：

1.divide it by 3 (it has to be divisible)

你在哪里测试整除性？

所以，这里有一个错误：

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也能解决问题，recurnece也不是必须的。只需以一种有趣的方式对数字进行排序：根据数字被 3 整除的次数降序排列，然后再按升序排列。所以，给你一个任务：用一个解决方案挑战你的老师，一旦读入数字，只执行一条指令 std::sort（或 qsort，正如我看到你用 C 写的那样），然后测试解决方案的有效性，并打印出来。

此外，我刚刚证明了如果存在解，那么它是唯一的。

我的代码有什么问题 [Dfs，动态规划]

what's wrong with my code [ Dfs , Dynamic programming ]

c++

dynamic-programming

depth-first-search