反转表算法（具体要求看内容）
内容：
由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;
}
static void Main(string[] args)
{
int[] listdata = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
permlist(listdata, 0, 9);
Console.ReadLine();
}
}
}
[解决办法]
本帖最后由 superdullwolf 于 2009-08-07 04:12:50 编辑 数学归纳法，先口算+笔算，得到规律，再实验，也有人称“驴式思考”：
1，从输入2 3 6 4 0 2 2 1 0 看，第一个数字是2，那么得到了a是{??1?????? }，因为1前边有2个比1大的，所以1只能排在第3个。
//得到了a是{??1?????? }
2，第二个数字是3，那么得到了a是{??1?2???? }
依次口算，用笔记录得到
a是{??1?2???3 }
得到了a是{??1?2?4?3 }
得到了a是{5?1?2?4?3 }
得到了a是{5?1?264?3 }
得到了a是{5?1?26473 }
得到了a是{5?1?26473 }
3，根据规律，心中有个大概的公式，尝试写代码
using System;
namespace ConsoleApplication3
{
class Program
{
static void Main(string[] args)
{
int[] b = new int[] { 2, 3, 6, 4, 0, 2, 2, 1, 0 };
int n = b.Length;
int[] a = new int[n];
for (int i = 0; i < n; i++)
{
//假设索引是这个数字
int index = b[i] ;
for (int j = 0; j <= index ; j++)
{
if (a[j]!=0)
{
index++;
}
}
a[index] = i + 1;
}
for (int i = 0; i < a.Length; i++)
{
Console.WriteLine(a[i]);
}
Console.ReadLine();
}
}
}
//实验成功
数学归纳法是常用的一种证明算法正确性的方法。
同样的，可以作为一种常见方法应用于程序正确性的证明
1.初始条件成立
2.程序执行过程中每一步符合某个不变式，这个不变式通常与程序期望结果符合的。
3.程序能够终止，并且终止的时候不变式的成立能够 和程序的期望结果符合。
（例如：一个满头秀发的人，不管他掉多少根头发，都不会不是秃头，这样就是悖论，因为不满足第3条）
这是很重要的思维方式，希望LZ以后多加利用，例如：
排列: 从n个对象中选出m个作为一种排列, 有A(n,m)种; 当m=n时,相当于求n个对象的全排列, 有n!种
组合: 从n个对象中选出m个作为一种组合, 有C(n,m)种; 当m=n时,只有一种.
这样的思路就可以写出排列和组合的输出算法。
归纳法的思想是很强的, c 程序书上, 简单的如求n的阶乘, 复杂的如汉诺塔. 特别是汉诺塔，九连环的问题,
不用递归的方法,很难解决这个古典难题. 但是汉诺塔的递归程序只有不到6,7行.
（这里不讨论非递归可以解决的问题和递归引起的时间空间开销）
以上程序复杂度是O(n*Σ(bi))
至于Σ(bi)是什么规律，我现在还没想清楚，这个题目是n=9,Σ(bi)=20
当n趋向无穷大的时候，可能最终总的复杂度接近O(n*n)吧，可以用大量数据画一下曲线观察一下。
[解决办法]
先做分折
这题应该反着来算
2 3 6 4 0 2 2 1 0 这个应该算是个位置信息
我们自己加上个反的序号
数字:1 2 3 4 5 6 7 8 9
位置:2 3 6 4 0 2 2 1 0
序号:8 7 6 5 4 3 2 1 0
这个序号的意义在与他列出如果数是从大到小即：9 8 7 6 5 4 3 2 1这样排之后
对应数字在他位置上在前面比他大的个数 所以 9 对 0（9最大前面没有比他小的）, 1对8（同理）
我的算法：
反着来看
1，数字是9,序号是0,位置是0, 9是最大的比他大个数的当然是0 {9}
2，数字是8,序号是1,位置是1 序号 = 位置 把数插在最后 {9,8}
3，数字是7,序号是2,位置是2 序号 = 位置 把数插在最后 {9,8,7}
4，数字是6,序号是3,位置是2 序号 > 位置 把数插在第2个后面 {9,8,6,7}
5，数字是5,序号是4,位置是0 序号 > 位置 把数插在第0个后面（第一个）{5,9,8,6,7}
6，数字4 同上 {5,9,8,6,4,7}
7，数字3 {5,9,8,6,4,7,3}
8，数字2 {5,9,8,2,6,4,7,3}
9，数字1 {5,9,1,8,2,6,4,7,3}
结束
[解决办法]
关注中......
[解决办法]
DHGGSGHF
[解决办法]
#include <iostream>
using namespace std;
int main( int argc, char* argv[] )
{
int anBigger[] = { 2, 3, 6, 4, 0, 2, 2, 1, 0 }, nResultCnt;
const int nSize = sizeof(anBigger) / sizeof(anBigger[0]);
int anResult[nSize], anRange[nSize][2], nBefore, nBehind, i, j;
for ( i = 0; i < nSize; anResult[i++] = -1 )
{// 取值范围的最小值为它前面至少有给定的比它大的数
anRange[i][0] = anBigger[i];
// 取值范围的最大值为最小值加上比它小的所有数
anRange[i][1] = anBigger[i] + i;
}
anRange[0][0] = anBigger[0];
anRange[0][1] = anBigger[0];
anResult[ anBigger[0] ] = 1;
for ( nResultCnt = 1; nResultCnt < nSize; )
for ( i = 1; i < nSize; ++i )
{
if ( anRange[i][0] == anRange[i][1] ) continue;
// 统计一定比它左且小于它的数
for ( nBefore = j = 0; j < i; ++j )
if ( anRange[j][1] < anRange[i][0] ) ++nBefore;
// 统计一定比它右且大于它的数
for ( nBehind = j = 0; j < i; ++j )
if ( anRange[j][0] > anRange[i][1] ) ++nBehind;
// 至少还有nSmallBefore个比它小的数在它前面
anRange[i][0] = anBigger[i] + nBefore;
// 如果最小值的位已经有确定解，则递增最小值，直到没有确定解为止
for ( ; anResult[ anRange[i][0] ] != -1; ++anRange[i][0] );
// 至少还有nSmallBehind个比它小的数在它后面
anRange[i][1] = anBigger[i] + i - nBehind;
// 如果最大值的位已经有确定解，则递减最大值，直到没有确定解为止
for ( ; anResult[ anRange[i][1] ] != -1; --anRange[i][1] );
if ( anRange[i][0] == anRange[i][1] )
{// 如果发现前后一样，则确定为一个解
nResultCnt++;
anResult[ anRange[i][0] ] = i + 1;
}
}
for ( i = 0; i < nResultCnt; ++i ) cout << anResult[i] << " ";
cout << endl;
system( "pause" );
}
