题目如下：
（ACM浙江大学网上的练习题，原版是英文的）
Let { A1,A2,...,An } be a permutation of the set{ 1,2,..., n}. If i < j and Ai > Aj then the pair (Ai,Aj) is called an "inversion" of the permutation. For example, the permutation {3, 1, 4, 2} has three inversions: (3,1), (3,2) and (4,2).
The inversion table B1,B2,...,Bn of the permutation { A1,A2,...,An } is obtained by letting Bj be the number of elements to the left of j that are greater than j. (In other words, Bj is the number of inversions whose second component is j.) For example, the permutation:
{ 5,9,1,8,2,6,4,7,3 }
has the inversion table
2 3 6 4 0 2 2 1 0
since there are 2 numbers, 5 and 9, to the left of 1; 3 numbers, 5, 9 and 8, to the left of 2; etc.
Perhaps the most important fact about inversions is Marshall Hall's observation that an inversion table uniquely determines the corresponding permutation. So your task is to convert a permutation to its inversion table, or vise versa, to convert from an inversion table to the corresponding permutation.
Input:
The input consists of several test cases. Each test case contains two lines.
The first line contains a single integer N ( 1 <= N <= 50) which indicates the number of elements in the permutation/invertion table.
The second line begins with a single charactor either 'P', meaning that the next N integers form a permutation, or 'I', meaning that the next N integers form an inversion table.
Following are N integers, separated by spaces. The input is terminated by a line contains N=0.
Output:
For each case of the input output a line of intergers, seperated by a single space (no space at the end of the line). If the input is a permutation, your output will be the corresponding inversion table; if the input is an inversion table, your output will be the corresponding permutation.
Sample Input:
9
P 5 9 1 8 2 6 4 7 3
9
I 2 3 6 4 0 2 2 1 0
0
Sample Output:
2 3 6 4 0 2 2 1 0
5 9 1 8 2 6 4 7 3
我的程序如下：
问题：编译、连接都通过，运行时输入两行数据后没有反应，经检查是因为程序中红字部分是死循环，这是为什么？
#include <iostream>
using namespace std;
// 函数声明， fun_p 用于处理输入为p的情况，fun_i 用于处理输入为i 的情况
void fun_p (int, int *);
void fun_i (int, int *);
int main ()
{
int arry[50];
int N;
char tmp;
cin>>N;
while (N > 0)
{
cin>>tmp;
for (int i = 0;i < N;i++)
{
cin>>arry[i];
}
switch (tmp)
{
case 'p':
case 'P': fun_p (N, arry); break;
case 'i':
case 'I': fun_i (N, arry); break;
default: cout<<"Error!"<<endl;
}
cin>>N;
}
return 0;
}
void fun_p (int N, int *p)
{
int p_arry[50];
for (int i = 1;i <= N;i++)
{
int count = 0;
for (int j = 0;j < N;j++) // 这是个死循环，为什么？？
{
while (*(p+j) != i && *(p+j) > i)
{
count++;
}
}
p_arry[i-1] = count;
}
for (i = 0;i < N;i++)
{
cout<<p_arry[i]<<" ";
}
cout<<endl;
}
// void fun_i 函数定义先不写了
void fun_i (int N, int *p)
{
}
[此贴子已经被作者于2005-11-22 13:55:47编辑过]
