程序设计大赛第二题： [复制链接]

求n个元素的排列，要求在排列中没有一个元素处于它应当占有的位置

是不是这个意思，1，2，3

1，2，3  //无效
1，3，2 // 无效
2，1，3 //无效
2，3，1
3，2，1  //无效
3，1，2

你这问题不属于Qt范围，属于汇编、C编程一类的。

简单

引用第2楼haulm于2009-06-05 12:46发表的  :
你这问题不属于Qt范围，属于汇编、C编程一类的。

也不属于……算算法或者离散吧

引用第1楼elba于2009-06-05 12:15发表的  :
是不是这个意思，1，2，3
1，2，3  //无效
1，3，2 // 无效
2，1，3 //无效
.......

2/3/1  是对的

3/2/1  是错的

不难，也不简单，要用到组合数学的算法

用的是c代码，回溯法
int const size = 6;

bool checkplace(int *board, int pos)
{
    if(pos == 0)
    {
        return true;
    }
    int i = 0;

    for(i = 0;i < pos; i++)
    {
        if((board == board[pos]) || ( board[pos] == pos ))
            return  false;
    }
    return true;
}


void printout(int *board)
{
    int i = 0;

    for(i = 0; i < size; i++)
    {
            cout<<board;
    
    }
    cout<<endl<<endl;
}


void main()
{
    int board[size] = {0};
    int row = 0;
    int count = 0;

    while( row+1 )
    {
        board[row]++;

        while (    (board[row] <= size) && (checkplace(board, row) == false) )
        {
            board[row]++;
        }

        if(board[row] <= size)
        {
            if( row == size -1)
            {
                printout(board);
                count++;
            }                
            else
            {
                row++;
                board[row] = 0;
            }
        }
        else
        {
            row--;
        }
    }
    cout<<"The Number is "<<count<<endl;
    return ;
}

引用第7楼xiaodong于2009-06-07 18:54发表的  :
用的是c代码，回溯法
int const size = 6;
bool checkplace(int *board, int pos)
{
.......

测试了没有，代码 有很大问题！

这个的试想就是个2维矩阵
  1 2 3 4 5 6... （位置）
1 x o o o o o
2 o x o o o o
3 o o x o o o
4 ..............
（数)
x表示 左边的数 不能放在这个位子上

考虑中。。。

其实这个算法很实用的，加密算法就可以使用！

#include <QtGui>

int main(int argc, char *argv[])
{
    QApplication app(argc, argv);

    int m = 6;
    
    QVector<bool> flags(m+1);
    QStack<int> result;

    for(int i=0; i<=m; ++i)
    {
    flags = false;
    }
    int n=1;
    int number=2;

    while (n > 0)
    {
        if (flags.at(number) == 0 && number != n)
        {
            result.push(number);
            flags[number] = true;
            if (n == m)
            {
                qDebug() << result;
                n--;
                int tmp = result.pop();
                flags[tmp] = false;
                tmp = result.pop();
                flags[tmp] = false;
                number = (tmp+1)%m;
            }
            else
            {        
                n++;
                number = (n+1) % m;
            }
        }
        else if (number == n)
        {    if (result.size() != 0)
            {
                int tmp = result.pop();
                flags[tmp] = 0;
                number = (tmp+1) % m;
            }
                        n--;
        }
        else
        {
            number = (number+1) % m;
        }
                
        if (number == 0)
            number = m;

    }    
}
1) 还是回溯
2）可以把条件再规整一下
3）考虑一下 好更快的算法没

引用第11楼mmmou2000于2009-06-10 01:23发表的  :
#include <QtGui>
int main(int argc, char *argv[])
{
    QApplication app(argc, argv);
.......

有待测试，谢谢参与！

没人提出其他的 例程了么？

引用楼主sunvim于2009-06-05 11:33发表的 程序设计大赛第二题： :
求n个元素的排列，要求在排列中没有一个元素处于它应当占有的位置

这里竟然有程序大赛！！
我不写代码，楼主看看我的想法可不可行，谢谢！

1、n == 1 的话，无解；
2、n >= 2的话，将1，2。。。n这n个数排列成 n，n - 1，… 2，1；
3，判断n是否是奇数，如果不是奇数就排列完了，
   如果n是奇数的话，将步骤的排列结果的第一数(n)跟中间那个数（中间那个数等于(n + 1) /2）调换位置。

引用第13楼九重水于2009-06-10 20:53发表的  :
这里竟然有程序大赛！！
我不写代码，楼主看看我的想法可不可行，谢谢！
.......

同志，你把题目想的太简单了！好好看一下 前面的回帖吧

我倒过来数你的 偶数情况： 每个数都在其位置上……

其实是下面这个吧

n!+(-1)^1*(n-1)!*C(n,1)+(-1)^2*(n-2)!*C(n,2)-....+(-1)^(n-1)*1!*C(n,n-1)

是求出所有排列方式，还是只要一种？