我试图用dfs和动态编程来解决这个问题。然后我把代码提交给了我的学生，但答案是错误的。我是不是用dfs实现了一些错误。我的代码出了什么问题
PS。抱歉我的英语不好
问题：
给定一个随机数，有两种不同的方法可以处理数字
1.除以3(必须是可整除的(
2.乘以2给定n个数字，在交换前查找原始订单
----EXAMPLE1-----
输入：6
4 8 6 3 12 9
输出：9 3 6 12 4 8
----EXAMP2-----
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;
}
}
}
}
- OP应该首先告诉我们的信息：
我的代码只给出了10个测试用例中的7个测试用例的正确答案问我的老师，他只是告诉我要小心递归。但我不知道我的递归或其他
- 一个"；失败"：
这里有一个失败的案例：假设您有序列3 1 2 4。有效遗嘱对于4/3，返回true，因为它在序列中看到1。–Calculuswhich
- 更好的解决方案
#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 << " " ;
}
}
最黑暗的地方在灯下。
查看问题定义：
1.将其除以3(它必须是可分割的(
你在哪里测试可分割性？
因此，这里有一个错误：
if(valid(st/3)){
此测试应为：
if(st % 3 == 0 && valid(st/3)){
有了这个简单的改进，所有三个测试用例都通过了
改进(简化(解决方案的提示
不能被3整除的数字必须在可整除的后面。同样，那些不能被9整除的必须在那些能被9整整除的之后。类似地，对于27，81，。。。
现在，如果你把你的数字分成形式为n=3^k*m的数字子集，其中m%3！=0，则在每个这样的子集中，您的算法所允许的唯一操作是"0"；乘以2"；。所以按升序排列就足够了。
没有dfs就可以解决这个问题，递归也不是真正必要的。只需以一种有趣的方式排列数字：按照数字可被3整除的次数降序排列，然后按升序排列。因此，你的任务是：用一个解决方案挑战你的老师，一旦读入数字，只执行一个指令std::sort(或qsort，我看到你用C写的(，然后测试解决方案的有效性，并打印出来
此外，我刚刚证明，如果一个解决方案存在，它是独一无二的。