当前位置: 代码迷 >> 高性能计算 >> 反转表算法(具体要求视内容)
  详细解决方案

反转表算法(具体要求视内容)

热度:8686   发布时间:2013-02-26 00:00:00.0
反转表算法(具体要求看内容)
内容:
由1开始之连续数字a1.a2.a3...an相对有一反转表:b1.b2...bm。其bm代表意思为:数字m的位置前面有几个比大个个数。
2 3 6 4 0 2 2 1 0
第1个2为1前面有2个比它大的数
第2个3为2前面有3个比它大的数
第3个6为3前面有6个比它大的数....以此类推
所以答案为
5 9 1 8 2 6 4 7 3 
数字1前面有2个比它大的数 5 9
数字2前面有3个比它大的数 5 9 8
输入说明:
输入的每一行含有一个由m个数所组成的数列(反转表) 1<=m<=50,
单独一个 -1 在一行代表测试资料的结束
输出说明:
请输出从 1 到 m 所代表的数列
范例输入:

2 3 6 4 0 2 2 1 0

-1
范例输出 :
5 9 1 8 2 6 4 7 3

------解决方案--------------------------------------------------------
本帖最后由 superdullwolf 于 2009-08-07 04:09:32 编辑
全排列肯定能计算出结果来,不过复杂度是O(n!),肯定是慢的不行了。
全排列的写法: 

using System; 

namespace ConsoleApplication3 

    class Program 
    { 


        static void permlist(int[] listdata, int k, int m) 
        { 
            if (k == m) 
            { 
                for (int i = 0; i <= m; i++) 
                { 
                    Console.Write(listdata[i]); 
                } 
                Console.WriteLine(); 
            } 
            else 
                for (int i = k; i <= m; i++) 
                { 
                    Swap(ref listdata[k], ref listdata[i]); 
                    permlist(listdata, k + 1, m); 
                    Swap(ref listdata[k], ref listdata[i]); 
                } 

        } 


        static void Swap(ref int a, ref int b) 
        { 
            int temp = a; a = b; b = temp; 
        } 
  相关解决方案