一路坑爹的题目.

一道坑爹的题目.....

题目：从1--9中选取N个数字，组成不重复的N位数，从小到大进行编号，当输入其中任何一个数M时，能找出该数字对应

的编号。如N=3，M=213.
输出：
【123（1），132(2),213(3),231(4),312(5),321(6)】--->X=2.

我首先用全排列做，行不通，输出的结果并不是严格按照从小到大的顺序输出的，如N=3，M=321时

输出：【123（1），132(2),213(3),231(4),321(5),312(6)】--->X=5.

这是错误的，我也找到了错误的根源，但不知道怎么解决。

各路神仙有更好的方法没，当然也可以在我的这种方法上进行改进，不胜感激。

我的代码如下，但输不出真确结果：

C/C++ code


#include<iostream>
using namespace std;

void f(int*a,int n,int m,int t,int &bz,int &bz1)
{
    if(t==(n-1))
    {
        bz++;
        int sum=0;
        for(int i=0;i<n;i++)
        {
            cout<<a[i];
            sum=sum*10+a[i];
        }
        
        cout<<"("<<bz<<")"<<",";
        if(sum==m)
        {
            bz1=bz;
        }
        return;
    }
    else
    {
        for(int i=t;i<n;i++)
        {
            swap(a[t],a[i]);
            f(a,n,m,t+1,bz,bz1);
            swap(a[t],a[i]);
        }
    }
}
int main()
{
    int a[9];
    int n;
    cout<<"input N"<<endl;
    cin>>n;
    for(int i=0;i<n;i++)
        a[i]=i+1;
    int m;
    cout<<"input M"<<endl;
    cin>>m;
    cout<<endl;
    int bz=0,bz1=0;
         cout<<"[";
    f(a,n,m,0,bz,bz1);
    cout<<"\b]----->X=";
    cout<<bz1<<endl;
    return 0;
}

------解决方案--------------------

C/C++ code

#include <iostream>
using namespace std;

void Swap(int* p1, int* p2)
{
    int tmp = *p1; *p1 = *p2; *p2 = tmp;
}

void Reverse(int* start, int* end)
{
    while (start < end)
        Swap(start++, --end);
}

int NextPermutation(int* start, int* end)
{
    int* p, *sp = end - 2;
    if (start >= end - 1)
        return 0;
    while (sp >= start) {
        if (sp[0] < sp[1])
            break;
        --sp;
    }
    if (sp < start) {
        Reverse(start, end);
        return 0;
    }
    for (p = end - 1; p > sp; --p)
        if (*p > *sp) {
            Swap(sp, p);
            break;
        }
    Reverse(sp + 1, end);
    return 1;
}

int cmp(int v, int* array, int n)
{
    while (v) {
        if (v % 10 != array[--n])
            return 0;
        v /= 10;
    }
    return 1;
}

int main()
{
    int n, m, x, array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    cin >> n >> m;
    for (x = 1; NextPermutation(array, array + n); ++x) {
        if (cmp(m, array, n)) {
            cout << x << endl;
            break;
        }
    }
}

相关推荐