问题陈述：
输入格式：输入的第一行包含一个整数n。第二行输入包含 n 个数组元素
输出格式：所有数组元素可以组成的最大数
限制：1<=n<=100 and 1<=array elements<=1000
简单的排序算法不适用于以下输入：2,21 输出为 212，但最大数字为 221
因此我想出了以下算法：
升级函数根据以下基础返回一个值：
如果元素等于 1000，则返回 -1，这导致它被放置在数组的末尾
如果元素是单个数字并且等于其范围的 msd，我们返回 msd100 + msd10 + msd
如果元素是两位数并且等于 msd10 + msd，我们返回 msd100 + msd*10 + msd
如果元素是两位数，我们返回元素*10
在其他情况下我们返回元素
我想出了这个算法，考虑了输入 532, 5 , 55 ,56 最大数量应为 56,555,532
我的代码：
#include<stdio.h>
#include<stdlib.h>
void sort_msd(int arr[],int n);
void range_provider_msd(int arr[], int n); // finds out the indexes within which elements of same msd are present
void swap(int a,int b, int arr[]); // swaps array elements with index a and b in array arr[]
int msd(int n); //finds msd of n
void sort_final(int range_left,int range_right,int arr[], int msd_); //gives the final sort on the basis of upgrade function
int upgrade(int n,int msd_); //upgrades element for better comparison
int main()
{
int n; //n is number of element in array
scanf("%d",&n);
int*arr=(int*)malloc(n*sizeof(int));
for(int i=0;i<n;++i){scanf("%d",&arr[i]);}
sort_msd(arr,n); //soritng according to msd
range_provider_msd(arr,n);
for(int i=0;i<n;++i){printf("%d",arr[i]);}
return 0;
}
void sort_msd(int arr[],int n)
{
for(int i=0;i<n;++i)
{
int max_index=i,max_msd=msd(arr[i]);
for(int j=i+1;j<n;j++)
{
int compare_msd=msd(arr[j]);
if(compare_msd>max_msd)
{
max_index=j;
max_msd=compare_msd;
}
}
swap(i,max_index,arr);
}
}
int msd(int n)
{
while(n>=10)
{
n=n/10;
}
return n;
}
void swap(int a,int b, int arr[])
{
int temp=arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
void range_provider_msd(int arr[], int n)
{
//following code finds out the index ranges for elements with same msd and passes them onto the sort_final function
int left_range=0,right_range=0;
for(int i=1;i<(n+1);++i) //n+1 to check for the special case for last elements being equal
{
if(msd(arr[left_range])-msd(arr[i]) == 0 && left_range<n-1 && i<n)
++right_range;
else if(right_range== n-1 && i==n) //special code when last elements are equal
{
sort_final(left_range,right_range,arr,msd(arr[left_range]));
}
else
{
sort_final(left_range,right_range,arr,msd(arr[left_range]));
left_range=right_range+1;
++right_range;
}
}
}
void sort_final(int range_left,int range_right,int arr[],int msd_)
{
for(int i=range_left;i<=range_right;++i)
{
int max_index=i;
for(int j=i+1; j<=range_right;++j)
{
if(upgrade(arr[j],msd_)>upgrade(arr[max_index],msd_))
max_index=j;
}
swap(i,max_index,arr);
}
}
int upgrade(int n, int msd_)
{
if(n==1000)
return -1;
else if(n<10 && n==msd_)
return(100*msd_ + 10*msd_ + msd_);
else if(n>=10 && n<100 && n==(10*msd_+msd_))
return(100*msd_ + 10*msd_ + msd_);
else if(n>=10 && n<100)
return(n*10);
else
return(n);
}
我在评分系统上提交了这段代码，并在 11 次测试中的第 9 次测试中卡住了，并且测试没有指定我卡在哪些输入上。如何找到程序无法输出正确答案的情况？
或者有没有更简单、明显的方法来解决这个问题？我对数据结构或类似的东西一无所知。
p.s 这是我在加州大学圣地亚哥分校的 Coursera 课程“算法工具箱”中的作业之一。
如何找到程序无法输出正确答案的情况？
尝试
int n = 2;
int*arr=(int*)malloc(n*sizeof(int));
arr[0] = 56;
arr[1] = 561;
您的代码将给出
56156
但你本可以形成
56561
或者有没有更简单、明显的方法来解决这个问题？
OP 的代码展示了转换数组值以进行排序以完成任务的勇敢尝试。正如经常发生的那样，专注于给定的参数会导致人们忽视更简单的替代方案。可悲的是，尝试调试 OP 的代码只会让你进一步陷入兔子洞。
此问题是寻求“最佳”值的强力“排列”的案例研究。
它是“旅行商问题”的变体。
要破解的“难题”是寻找/编码一种算法来解决问题。数字用户输入的收集和验证不是问题。为简单起见，下面的代码使用示例数据的编译时string表示。将值数组转换为等效的字符串作为读者的练习。
#include <stdio.h>
#include <string.h>
char *elements[] = { "532", "5", "55", "56" }; // sample data
const int nElements = sizeof elements/sizeof elements[0];
int used[ nElements ]; // flags denoting availability of each element during recursion
char out[ 128 ]; // big enough to serve this example
void go( size_t k, char *p ) {
// working copy of string, so far
char wrk[ 128 ], *at = wrk + strlen( strcpy( wrk, p ) );
for( size_t i = 0; i < nElements; i++ )
if( !used[i] ) { // grab next available element
strcpy( at, elements[ i ] ); // in turn, 'tack' each element as a suffix
if( k+1 == nElements ) { // at the extent of recursion
if( strcmp( wrk, out ) > 0 ) { // is this "better" (ie. "larger")?
strcpy( out, wrk ); // preserve as "best so far"
// puts( out ); // debugging showing improving results
}
return;
}
used[i] = 1; // mark this element 'used'
go( k+1, wrk ); // next level, please
used[i] = 0; // this element now available
}
}
int main( void ) {
go( 0, out );
puts( out ); // the final result
return 0;
}
启用“进度调试”的结果：
53255556 // notice each reported value is larger than the previous
53255655
53256555
55325556
55325655
55553256
55556532
55653255
55655532
56532555
56553255
56555532
56555532 // final result
为了清楚起见，这里忽略了通常禁止使用“全局变量”的规定。变量可以作为（混乱的）参数传递给
go()注意：如果有 1000 个元素，每个元素可能有 3 位长，很明显这段代码的微小缓冲区将无法工作。也许另一个练习是明智地分配足够的动态存储。也许另一个练习是只使用两个缓冲区；一个表示“到目前为止”取得的结果，另一个表示当“弹出”一级递归时“清理”（重新终止）。
编辑：
上面的代码将尝试所有排列，即使先前的排列可能是“345678...”，并且当前版本的前缀为“345111...”。显然，这次探索的最终结果将比已经取得的成果要少。对此的进一步工作（许多级别的排列）将是毫无意义的。读者的另一个练习可能是及早发现这种情况并“修剪”对该树分支的搜索。
或者有没有更简单、明显的方法来解决这个问题
如果您正在寻找新的算法，请检查这些代码是否满足您的测试用例（请根据您的要求修改输出方法，在我的代码中，最后，我已将最大可能的整数打印到STDOUT）：
#include <stdio.h>
#include <string.h>
char *cmp(char *n1, char *n2)
{
char n1_n2[9] = "", n2_n1[9] = "";
strcat(n1_n2, n1);
strcat(n1_n2, n2);
strcat(n2_n1, n2);
strcat(n2_n1, n1);
int r = strcmp(n1_n2, n2_n1);
if (r < 0) return n2;
else return n1;
}
void sort(int n, char arr_str[][5])
{
for (int i=0; i<n; i++)
{
int idx = i;
for (int j=i+1; j<n; j++)
{
char *r = cmp(arr_str[j], arr_str[idx]);
if (r == arr_str[j])
{
idx = j;
}
}
char temp[5];
strcpy(temp, arr_str[idx]);
strcpy(arr_str[idx], arr_str[i]);
strcpy(arr_str[i], temp);
}
}
int main()
{
int n;
scanf("%d", &n);
char arr_str[n][5];
for (int i=0; i<n; i++)
{
scanf("%s", arr_str[i]);
}
sort(n, arr_str);
for (int i=0; i<n; i++)
{
printf("%s", arr_str[i]);
}
printf("\n");
return 0;
}
def cmp(n1, n2):
n1_n2 = n1 + n2
n2_n1 = n2 + n1
return [n1, n2][n2_n1 > n1_n2]
n = int(input())
arr = list(input().split())
for i in range(n):
index = i
for j in range(i+1, n):
r = cmp(arr[index], arr[j])
if r == arr[j]:
index = j
temp = arr[index]
arr[index] = arr[i]
arr[i] = temp
result = [""]
for i in arr:
result[0] += i
print(result[0])