求一道算法题
题目是这样的，已知一个整数集合T，集合中可以包括0到9之间任意数，集合中数字不重复。现在给出一个整数N，大小按int类型，算法要求是：从上面集合中取出数字所能组成的整数中，比给出的N大的集合里面，最小的那个整数。比如，整数集合T=『1，2，3』，整数N=300，那么要从集合中取出数字所组成的整数应该是311；再如：T=『1』，N=56，那么要得到的整数应该是111（也就是说集合里面的数可以取多次）；
多谢大家能给点儿想法。
[解决办法]
首先不妨设定N=a1a2a3...aM，M位,集合为T
从最高位a1看起，一直看到最后一位aM
（1）在此过程中，一旦有一位（设为ai),满足ai>max{Tj},也就是ai大于集合T中所有的元素，则停止探寻，只需要
在集合T中构造出M+1位的最小的数，即为所求。
(2)在此过程中，一旦有一位（设为ai),满足ai<max{Tj}，也就是ai小于集合T中所有的元素，则可判定所求的数
也是M位，则继续探寻下面的数，且从ai这一位开始满足这样的法则,在T中找到比ai大的元素中最小的元素k，找出
以k为首位的位数等于（M-i+1）的最小数，作为所求数的后（M-i+1)位数
（3）在此过程中，一旦有一位（设为ai),满足ai=max{Tj},则继续探寻。当然，如果是对应刚才的（2），则所求的数的前（i-1）位都为max{Tj},也就是保留作为所求数的一部分，继续往下看。如果是对应刚才的情况（1），就是暂时放到那里，继续往下看（我相信到底该怎么解决这两种情况只是一个技巧问题，程序中你应该能解决）
下面给你几个例子
N=55557 T={1,2,4,5}
从N的最高位5看，一直对应情况3,直到7,7>5,所以归到情况1，所求的数应该为111111
N=555278 T={1,2,4,5}
从N的最高位5看，一直对应情况3,直到2,2<5,所以归到情况2，所求的数应该为555411
[解决办法]
从右往左搜貌似会快一点
如果aM < max{Tj} 则调整aM为刚好比aM大的集合中的数字就OK了
如果aM >= max{Tj} 则继续看高一位aM-1
如果aM-1 < max{Tj} 则调整aM-1为刚好比aM-1大的集合中的数字，aM为集合中最小的数字
如果aM-1 >= max{Tj} 则继续看高一位aM-2
。。。。。。
直到a1
如果1 < max{Tj} 则调整aM-1为刚好比1大的集合中的数字，a1后的数字都为为集合中最小的数字
如果a1 >= max{Tj} 则有M+1位且都为集合中最小的数字
[解决办法]
[解决办法]
/*
程序只考虑了处理逻辑，结构可以稍微修饰一下
*/
#include <iostream>
using namespace std ;
// A中最小元素
int SmallestElem(char A[], int n)
{
return A[0] ;
}
// 获得在集合A中，>=ai的最小元素，如果不存在，返回-1
int GetSmallest_EqaualLargerThanAi(char A[], int n, int ai)
{
int i = 0 ;
for(; i<n; i++)
{
if(A[i] >= ai)
break ;
}
return i==n?-1:A[i] ;
}
// 将结果B中从s到e的设置为A集合中最小元素
int SetLowerB(char B[], int s, int e, char A[], int an)
{
for(; s<e; s++)
{
B[s] = SmallestElem(A, an) ;
}
}
// 递归过程
int Recursion(char A[], int an, char N[], int nn, int i, char B[])
{
if (i<nn)
{
int ai = N[i] ; // 当前位
int si = GetSmallest_EqaualLargerThanAi(A, an, ai) ;// 获得>=ai的元素
if(si == -1) // 需要 “进位”
{
SetLowerB(B, i, nn, A, an) ; // 设置后续为最小元素
return 1 ; // 进位返回1
}
int res = Recursion(A, an, N, nn, i+1, B) ; // 递归处理后续位数,res=1表示后续位数产生“进位”
si = GetSmallest_EqaualLargerThanAi(A, an, si+res) ;
if (si == -1)
{
SetLowerB(B, i, nn, A, an) ;
return 1 ;
}
else
{
B[i] = si ;
return 0 ; // 没有“进位”
}
}
return 0 ;
}
// 辅助函数
void Output(char B[], int n)
{
for(int i=0; i<n && B[i]!='F'; i++)
{
std::cout<<B[i];
}
std::cout<<endl ;
}
int main(void)
{
char A[] = {'1','2','3'} ;
char N[] = {'3','4','4'} ;
char B[100] ;
for(int i=0; i<sizeof(B); i++)
{
B[i] = 'F' ;
}
int res = Recursion(A, sizeof(A)/sizeof(char), N, sizeof(N)/sizeof(char), 0, B) ;
if(res == 1)// 最高位需要“进位”
std::cout<<"1" ;
Output(B, sizeof(B));
return 0 ;
}
[解决办法]
我搞了半天终于写出来了，应该没多大问题。
#include<iostream>
#include<stdlib.h>
using namespace std;
int comp(const void *p, const void *q)
{
return ( *(int*)p > *(int*)q );
}
void Divide(int Digit[], int X, int &N)
{
while(X > 0)
{
Digit[N++] = X % 10;
X /= 10;
}
}
int Sum(int Set[], int pos, int N)
{
int val = 0;
for(int i = 0; i < N; i ++)
{
val = 10 * val + Set[pos];
}
return val;
}
bool Check(int rec[], int Digit[], int pos, int n)
{
for(int i = 0; i < pos; i ++)
{
if(rec[i] > Digit[n-1-i])
{
return true;
}
}
return false;
}
void Find(int Set[], int m, int Digit[], int pos, int n, int &min, int X)
{
static int sum = 0;
static int rec[10];
if(pos == n && sum != X)
{
min = min < sum ? min : sum;
}
for(int i = 0; i < m; i ++)
{
if(pos < n && ( Set[i] >= Digit[n-1-pos] //当前位 >= X对应位上的数字
|| pos > 0 && Check(rec, Digit, pos, n) )) //如果高位已经存在大于X对应位上的数字，则下一位只需要用最小的数字
{
sum = 10 * sum + Set[i];
rec[pos] = Set[i];
Find(Set, m, Digit, pos+1, n, min, X);
rec[pos] = -1;
sum /= 10;
}
}
}
void main()
{
int Set[4] = {1, 2, 3, 4};
int Digit[10];
int X = 3468;
int M = sizeof(Set) / sizeof(*Set);
int N = 0;
qsort(Set, M, sizeof(int), comp);
Divide(Digit, X, N);
int min = Sum(Set, M-1, N);
if(min <= X)
{
cout << Sum(Set, 0, N+1) << endl;
}
else
{
Find(Set, M, Digit, 0, N, min, X);
cout << min << endl;
}
}
[解决办法]
我靠，怎么没人回帖？全挂了？
