| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 5350 人关注过本帖, 1 人收藏
标题:看了上次的回文串排序有感而发,出个题大家玩玩
只看楼主 加入收藏
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:15 
算法思想是归并排序么~3次~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-03-24 10:54
ehszt
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:40
帖 子:1745
专家分:3216
注 册:2015-12-2
收藏
得分:0 
回复 11楼 九转星河
我也不知道用什么算法,但我知道结果。
2017-03-24 11:11
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
目前没想到啥好算法,状态压缩+DFS寻找最短路径。

将数组的每种形态使用五位数或康托展开存储,然后DFS寻找最短路径。

麻烦的是状态转换的可能,尤其数组移动感觉很恶心。

程序代码:
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define  M  5

int ws[120] = {1};

void print(int s[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        printf("%d%c", s[i], "\n "[i < n - 1]);
    }
}

static int fac[] = {1, 1, 2, 6, 24, 120};

/*

 * 康托展开

 */
int cantor(int sa[M])
{
    int result = 0;
    for (int i = 0; i < M; i++)
    {
        int count = 0;
        for (int j = i + 1; j < M; j++)
        {
            count += sa[i] > sa[j];
        }
        result += count * fac[M - i - 1];
    }
    return result;
}

/*

 * 逆康托展开

 */
void unCantor(int sa[M], int x)
{
    int i, j, l, t, h[10] = {0};

    for (i = 1; i <= M; i++)
    {
        t = x / fac[M - i];
        x -= t * fac[M - i];

        for (j = 1, l = 0; l <= t; j++) if (!h[j]) l++;

        h[--j] = 1, sa[i - 1] = j;
    }
}

void swap(int sa[M], int beg, int end, int to)
{
    int lren = end - beg + 1, sren[lren];
    for (int i = beg; i <= end; ++i) sren[i - beg] = sa[i];

    int stil[M - end + beg - 1], ltil = 0;
    for (int i = 0; i < M; ++i)
    {
        if (i >= beg && i <= end) continue;
        stil[ltil++] = sa[i];
    }

    int pos = 0;
    for (int i = 0; i < to; ++i) sa[pos++] = stil[i];
    for (int i = 0; i < lren; ++i) sa[pos++] = sren[i];
    for (int i = to; i < ltil; ++i) sa[pos++] = stil[i];
}

void dfs()
{
    int sa[M], queue[120] = {0}, f = 0, r = 1;

    while (f < r)
    {
        int now = queue[f++];

        for (int beg = 0; beg < M; ++beg)
        {
            for (int end = beg; end < M; ++end)
            {
                for (int to = 0; to < M - end + beg; ++to)
                {
                    unCantor(sa, now);
                    swap(sa, beg, end, to);
                    int next = cantor(sa);

                    if (ws[next]) continue;

                    queue[r++] = next;
                    ws[next] = ws[now] + 1;
                }
            }
        }
    }
}

int main()
{
    int sa[M];

    dfs();

    for (int i = 0; i < 120; ++i)
    {
        unCantor(sa, i);
        printf("step: %d   ", ws[i]);
        print(sa, M);
    }

    return 0;
}


[fly]存在即是合理[/fly]
2017-03-24 15:28
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 13楼 azzbcc
我想这种算法可以适用于任意排列的情况~如果安照楼主顺序变逆序的排列感觉应该很简洁才对~还是看看楼主是怎么认为的~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-03-24 17:22
ehszt
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:40
帖 子:1745
专家分:3216
注 册:2015-12-2
收藏
得分:0 
回复 13楼 azzbcc
用了四步,不对哦,用四步的话我完全可以把1后面的数往前插。
结果小于四步,不然也不会拿出来考大家。曾经高中时,有人拿扑克牌来考我,结果我一下午都没搞出来。
我想计算机可能能实现,就是算法不太好想。
我想了一个算法,不知可不可行。12345逆序数为0,54321逆序数为10,我们直接在3次以下凑这个逆序数的加减就可以了。


[此贴子已经被作者于2017-3-25 01:03编辑过]

2017-03-24 17:23
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
收藏
得分:15 
百度到的(方括号中的数据要移到*号位置):
第一步:*1 2[3 4]5
第二步:3*4 1[2 5]
第三步:*3 2[5 4]1
  结果:5 4 3 2 1

按数据块移动,3次可完成,可是块移不还是要一个个元素移动吗?代码实际操作还要移动6次还不如一个个元素移动呢。
2017-03-24 20:55
ehszt
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:40
帖 子:1745
专家分:3216
注 册:2015-12-2
收藏
得分:0 
回复 16楼 xzlxzlxzl
你拿扑克牌12345,三次就能排序。
我只是想用计算机算出这个过程。
2017-03-24 21:08
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
想了很久也想不到什么好的算法~用BFS记录每次移动变化后数据的集合~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-03-24 22:09
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
收藏
得分:15 
程序代码:
S(1) = 0            1    
S(2) = 1            12            21
S(3) = 2            123            321
S(4) = 3            1234        4321
S(5) = S(1)    + 3        12345        1 2345     54321
S(6) = S(2) + 3        123456        12 3456        654321
S(7) = S(3) + 3        1234567        123 4567     7654321

S(n) = S(n-4) + 3
2017-03-24 23:13
吹水佬
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:451
帖 子:10609
专家分:43210
注 册:2014-5-20
收藏
得分:15 
以下是引用xzlxzlxzl在2017-3-24 20:55:40的发言:

百度到的(方括号中的数据要移到*号位置):
第一步:*1 2[3 4]5
第二步:3*4 1[2 5]
第三步:*3 2[5 4]1
  结果:5 4 3 2 1

按数据块移动,3次可完成,可是块移不还是要一个个元素移动吗?代码实际操作还要移动6次还不如一个个元素移动呢。

变换一下,用数值交换形式可否:
图片附件: 游客没有浏览图片的权限,请 登录注册

#include <stdio.h>
void swap(short *p1, short *p2)
{
    *p1 ^= *p2;
    *p2 ^= *p1;
    *p1 ^= *p2;
}

main()     
{     
    char a[]="12345";
    swap((short*)a, (short*)(a+2));
    printf("%s\n", a);
    swap((short*)(a+1), (short*)(a+3));
    printf("%s\n", a);
    swap((short*)a, (short*)(a+2));
    printf("%s\n", a);
}

[此贴子已经被作者于2017-3-24 23:46编辑过]

2017-03-24 23:39
快速回复:看了上次的回文串排序有感而发,出个题大家玩玩
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.020674 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved