hmmm~~一个C语言编程题~~

Renee

先来段音乐~~

如果无法播放，请点击此处在新窗口打开

无聊的人可以来做做看啦~~

要求~~编写以下函数

[codes=c]
int PalindromeIt(char *s);

[/codes]

规则:

参数字符串s由任意单字节字符组成~~

字符串s中任意两相邻字符可以交换位置~~交换次数不限~~

如:ABCD可以AB交换为BACD~~A还可以继续和C交换~~变成BCAD~~

要求该函数实现以下功能:

1]判断给出的参数字符串s能否通过上述交换变成回文字符串~~如能则返回最少交换步数~~如不能则返回-1~~

所谓回文字符串:既从左往右读和从右往左读完全相同的字符串~~如ABCCBA、3213123以及ABCBA等等~~

2]用最少交换步数把s交换成回文字符串~~必须使用规则中规定的交换法~~


要求写出函数并简要说明算法~~

cyber

二级c没有过的飘过 下学期继续

hmmm

发给我的吗？

hyp

蛮难的~呃,不知道有期限吗~我现在要写一个论文55555555

Renee

没有期限~~

zhuzeitou

555555要最少步数啊………………
感觉好难………………

Renee

和冒泡排序很类似~~但还是有点区别的呢~~

比方说~~EABACABAE是可以接受的~~但冒泡排序却非得排成EAABCBAAE~~因为2个A是相等的~~就会被冒泡到一起~~实际上按照题意有间隔也不要紧~~只要保持2边对称即可~~

白银の式神

實際上。偶已經想到很多方法了。不過還咩證明是否素最少次數。

amp34

此内容已跳票。

白银の式神

渣A居然會看書。

Renee

很好啊~~那某A来给个算法罢~~

看门的老头

五笔A为啥会打出啊哈这两个字

amp34

事实上，在我发完以后就不记得具体的章节了。不过有出现过类似的内容倒素真的。

你们难道一直在等我发帖么？回复这么快。

amp34

在读了10分钟的题目以后，发现果然素类似而不素完全一样的题目。嗯嗯。

Renee

再附送一段音乐罢~~

zhuzeitou

555555刚才用java写了一个额………………

[codes=java]int PalindromeIt(char[] s){
    int count = 0;
    int l = s.length;
    int odd = 0;
    for (int i = 0; i < l / 2; i++){
        if (s != s[l - 1 - i]){
            for (int j = i + 1 , k = 0; j< l && k == 0; j++){
                if (s == s[j] && (s[j] != s[l - 1 - j] || j + j + 1 == l)){
                    s[j] = s[l - 1 - i];
                    s[l - 1 - i] = s;
                    k++;
                    count++;
                }
                if (j == l - 1 && k == 0){
                    odd++;
                    if (odd > l - l / 2 * 2){
                        return -1;
                    }
                    char temp = s[l / 2];
                    s[l / 2] = s;
                    s = temp;
                    i = i - 1;
                    count++;
                }
            }
        }
    }
    System.out.println(s);
    return count;
}[/codes]

算法就是从头开始判断元素是否对称，如果不对称，就寻找下一个不对称且相同的元素，并且交换
如果找不到，就说明此元素出现次数为奇数次，那么判断奇数个数的元素有多少个，如果比数组长度除2的余数大，就说明不满足是回文数的条件，返回-1；否则就与中间的那个元素交换，并重新从这一项开始判断
循环到中间项中止

不过不知道是不是最小步数额