完美的代价.doc

“程序设计”综合编程实验报告 （ 2010- 2011学年第 2 学期）实验项目名称： 完美的代价 学生姓名： 吴云川 专业班级： 信管1002 学号： 31001406 实验成绩： 一、实验内容与要求回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。有人认为回文串是一种完美的字符串。现在给你一个字符串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个回文串。这里的交换指将字符串中两个相邻的字符互换位置，例如所给的字符串为mamad，第一次交换ad，得到mamda；第二次交换md，得到madma；第三次交换ma，得到madam （回文！完美！）输入要求：程序要求从键盘读入数据。第一行是一个正整数N（N = 8000），表示所给字符串的长度，第二行是所给的字符串，长度为N且只包含小写英文字母。输出要求：如果所给字符串能经过若干次交换变成回文串，则输出所需的最少交换次数；否则，输出Impossible。二、问题分析1、程序的功能要求:将符合回文串条件的字符串以最少次数交换，输出其所需要的次数。如果碰见不能变成回文串的字符串，输出Impossible。2、程序的错误处理:对输入数据范围需要进行检测(字符串的长度不能超过8000)3、程序的性能要求：要求输出的次数为最少的交换次数。 三、方案设计1、解题思路（1） 输入一组N长度的字符串。（2）判断该字符串中每个字母出现的次数。 a.如果所有字母出现偶数次，那么该字符串可以进行字符间的交替，成为回文串。 b.如果有一个字母出现奇数次，那么该字符串也可以进行字符间的交替，成为回文串。 c.如果有两个字母或者两个字母以上出现了奇数次，那么该字符串不能通过字符间的交替成为回文串。（3）如果出现了a,b情况，那么就将字符串进行交替成为回文串，出现c就直接输出Impossible。（4）最后将在a,b情况下，交换的次数输出。2、数据结构描述 将字符串以一维数组的形式储存，大小为8001以为还要一个储存“n”。而每个字符出现的次数也以一维数组的形式储存，大小为26。3、程序框架结构 一个主函数int main(void)/*主要就行判断是否能成为回文串*/一个自定义函数int changes(char s,char x,int n);/*将字符串转换成回文串，然后输出交换的次数*/一个全局变量X，用于保存出现了奇数次的字符。4、关键算法描述结 束将changes返回给主程序判断i是否等于(n-1)/2将交替的次数累加到changes上统计每字母出现奇数的次数函数为k，将出现奇数次的字符赋值给x主函数结束输 出交替次数否是输出Impossible判断k是否大于等于2.输入一组字符串函数为si统计字符串中每个字母出现的次数函数为bj输入交换的次数为0找到字符后将其逐个向左移动找到字符后将其逐个向右移动在字符串左边第i个位置开始，向右寻找与第n-i-1位置相同的字符。在字符串右边第n-i-1个位置开始，向左寻找与之相同的字符。从左边第i的字符串开始逐个开始与x比较是否相等四、测试用例测试用例1：10输入：aabbddeeff输出：20测试用例2：17输入：readvbdfreavbfuui输出：43测试用例3：2输入：bj输出：Impossible测试用例4：7输入：abddefj输出：Impossible五、附源代码#includeint changes(char s,char x,int n);char x=0;int main(void)int n,i,k=0,b26=0,j;char y,s8001=0;scanf(%d,&n);getchar();for(i=0;in;i+) scanf(%c,&si);for(i=0;in;i+) j=si-a; bj+;for(j=0;j=2)printf(Impossiblen);elseprintf(%dn,changes(s,x,n);return 0;int changes(char s,char x,int n)int i,change=0,j,k;for(i=0;in/2;i+)if(si=x)for(j=i;ji;k-)sk=sk-1;si=sn-i-1;elsefor(j=n-i-1;j=i;