這一題題目有些長，不過這不影響它是一道水題。
題意描述：
題中描述了兩種情況，當輸入數據以'P'開頭時，表示輸入的是1~N的一個排列，要求輸出每個數前面比該數大的數字的個數，輸出結果時順序為數字1的在前，數字N的在最后。第二種情況正好相反，給出每個數字前面比該數大的數字的個數，要求輸出原序列。
第一種情況好說，主要是第二種情況。情況二的解法是按從后往前順序確定原序列，即先確定數字N的位置，再確定數字N-1的位置……直到所有數字位置確定。期間主要是元素的插入操作。
#include<stdio.h>
#include<stdlib.h>
#define LEN 60
int num[LEN]; //輸入，
int rs[LEN];//所求結果，兩種情況的結果都用rs[]記錄。
int N;
void fP()
{
int i, j, k;
int ps;
for(i = 1; i <= N; i++)
{
ps = 0;
while(num[++ps] != i);
int count = 0;
for(k = 1; k < ps; k++)
if(num[k] > i)
count++;
rs[i] = count;
}
}
void Insert(int ps, int insertnum, int len)//插入函數
{
int i, j;
for(i = len; i >= ps; i--)
rs[i + 1] = rs[i];
rs[ps] = insertnum;
}
void fI()
{
int i, j;
int len;
rs[1] = N;
len = 1;
for(i = N - 1; i >= 1; i--)
{
int ps = num[i] + 1;
Insert(ps, i, len);
len++;
}
}
int main()
{
int i, j;
char c;
scanf("%d", &N);
while(N != 0)
{
getchar();
c = getchar();
for(i = 1; i <= N; i++)
scanf("%d", &num[i]);
if(c == 'P')
fP();
else
fI();
for(i = 1; i < N; i++)
printf("%d ", rs[i]);
printf("%d\n", rs[i]);
scanf("%d", &N);
}
//system("pause");
}posted on 2012-08-02 16:19
小鼠標 閱讀(238)
評論(0) 編輯 收藏 引用 所屬分類:
水題