首页 / 算法 / C/C++语言算法题——替换
C/C++语言算法题——替换
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C/C++语言算法题——替换，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3399字，纯文字阅读大概需要5分钟。
内容图文
【问题】
Description
给定一个有限长度的非负整数序列。一次操作是指从第一个元素开始，依次把数列中的每个数替换为它右边比它小的数的个数。对该数列不断进行这个操作。总有一个时刻该数列将不再发生改变（即此时每个数都恰好等于它右边比它小的数的个数）。例如给定数列：
5,
44, 19, 6, 49, 1, 27, 19, 50, 20
连续进行五次操作后，依次得到新数列如下：
1, 6, 2, 1, 4, 0, 2, 0, 1, 0
3, 8, 5, 3, 5, 0, 3, 0, 1, 0
4, 8, 6, 4,
5, 0, 3, 0, 1, 0
5, 8, 7, 5, 5, 0, 3, 0, 1, 0
5, 8, 7, 5, 5, 0, 3, 0, 1,
0
其中，第四次操作后，数列不再发生改变。
对给定数列，循环执行上述操作，直到其不再改变为止，输出最后得到的数列。
Input
第1行：一个整数T（1≤T≤10）为问题数。
对于每组测试数据：
第1行是一个正整数：数列长度N ( 2 < N≤30
)；
第2行有N个正整数：分别为该数列第1至第N个元素的值a1,a2,…,aN( a1,a2,…, aN均为1 -
1000的数)，每两个整数之间用一个空格分开。
Output
对于每个问题，输出一行问题的编号（0开始编号，格式：case #0:
等）。
然后在一行中依次输出最后数列的所有元素，每两个元素之间用一个空格分开，最后一个元素后面没有空格。
Sample Input
3
10
5 44 19 6 49 1 27 19 50 20
10
3 2 7 10 9 8 8 5 1
5
10
12 12 19 19 7 10 9 6 18 9
Sample Output
case #0:
5 8 7 5 5 0 3 0 1 0
case #1:
9 2 3 6 5 3 3 2 0 0
case
#2:
6 6 6 6 3 4 3 0 1 0
【解题报告】
算法本身很容易实现，但是问题是我不清楚应当如何判断算法何时结束，也就是如何判断“两次变换所得到的新数组相等”。如果有更好的算法请不吝赐教。
1 #include <iostream>
2usingnamespace std;
3#define TRUE 1
4#define FALSE 0
5 6int isSame(constint*, constint*, constint);
7void setArray(int*, int);
8void outputArray(constint*, constint);
9void process(int*, int);
10int* clone(constint*, int);
11 12int main()
13{
14int T;
15 cin>>T;
16for(int c = 0; c < T; c++)
17 {
18int N;
19 cin>>N;
20int* arr = newint[N];
21 setArray(arr,N);
22for(;;) /* 这里我实在想不出该如何简便地判断参加变换的数组是否发生变化，因此 */ 23 { /* 只能通过备份前一次变换的结果和当次运算结果作比较 */ 24int* temp = clone(arr,N);
25 process(arr,N); /* 虽然能够AC，但是这肯定不是最优的算法 */ 26if(isSame(arr,temp,N)) /* 因此如有更好的，时间复杂度更低的算法还望不吝赐教奥 */ 27 {
28 delete[] temp;
29break;
30 }
31 }
32 cout<<"case #"<<c<<":"<<endl;
33 outputArray(arr,N);
34 delete[] arr;
35 }
36return0;
37}
38 39/** 判断两个同等长度的数组是否相等
40 @param arr1 数组1
41 @param arr2 数组2
42 @param N 数组1和2的长度
43 @returns 相等返回1，否则返回0
44*/ 45int isSame(constint* arr1, constint* arr2, constint N)
46{
47for(int i = 0; i < N; i++)
48 {
49if(arr1[i] != arr2[i])
50return FALSE;
51 }
52return TRUE;
53}
54 55/**
56 通过标准输入设置数组的各元素
57 @param arr 待填充的数组
58 @param n 数组长度
59*/ 60void setArray(int* arr, int n)
61{
62int t;
63for(int i = 0; i < n; i++)
64 {
65 cin>>t;
66 arr[i] = t;
67 }
68}
69 70/**
71 输出数组
72 @param arr 要输出的数组
73 @param N 数组长度
74*/ 75void outputArray(constint* arr, constint N)
76{
77for(int i = 0; i < N; i++)
78 {
79 cout<<arr[i];
80if(i != N-1) cout<<‘‘;
81else cout<<‘\n‘;
82 }
83}
84 85/**
86 处理算法
87 循环处理每一个元素，将其修改为它后面比它小的元素的个数
88 @param arr 要处理的数组
89 @param N 数组长度
90*/ 91void process(int* arr, int N)
92{
93for(int i = 0; i < N; i++)
94 {
95int count = 0;
96for(int j = i+1; j < N; j++)
97 {
98if(arr[j] < arr[i])
99 count++;
100 }
101 arr[i] = count;
102 }
103}
104105/**
106 克隆数组，将一个数组克隆为另一个数组，
107 使得两个数组中的各元素相同，但他们的首指针不同。
108 @param arr 待克隆的源数组
109 @param N 数组长度
110 @returns 克隆出的新数组
111*/112int* clone(constint* arr, int N)
113{
114int* temp = newint[N];
115for(int i = 0; i < N; i++)
116 {
117 temp[i] = arr[i];
118 }
119return temp;
120 }解题代码
【优化】
根据hoodlum1980的建议。将process函数改为
bool process(int* arr, int N)
{
bool changed = false;
for(int i = 0; i < N; i++)
{
int count = 0;
for(int j = i+1; j < N; j++)
{
if(arr[j] < arr[i])
count++;
}
if(arr[i] != count)
{
arr[i] = count;
changed = true;
}
}
return changed;
}
主函数相应部分改为
while(process(arr,N));
出处：http://acm.cs.ecnu.edu.cn/problem.php?problemid=2993
原文：http://www.cnblogs.com/ryuasuka/p/3514632.html
内容总结
以上是互联网集市为您收集整理的C/C++语言算法题——替换全部内容，希望文章能够帮你解决C/C++语言算法题——替换所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。