故乡的风 发表于 2013-7-19 10:16:54

算法一日一练 01

在一维数组A中顺序存放两个线性表(a1,a2, a3, ... , am)和(b1, b2, b3, ... , bn)，编写函数，将两个线性表位置互换，即将(b1, b2, b3, ... , bn)放在(a1,a2, a3, ... , am)前面。
试着设计在时间及空间两方面都尽量高效的算法，并将想法及源码贴出来（语言不限，最好C/C++）。我将适量给予评分，希望大家踊跃参与。

qiusuo 发表于 2013-7-19 18:08:55

我负责顶贴

囩戨 发表于 2013-7-19 19:53:47

路过。。得分。。。

Potato丶 发表于 2013-7-20 10:14:39

void exchangelist(int *list,int m,int n)
{
      void exch(int *list , int i ,int j);
      int i=0,j=m+n-1;
      
      exch(list,i,j);
      
    exch(list,i,n-1);
      
      exch(list,n,j);
      
}

void exch(int *list , int i ,int j)
{
      int temp;
      while (i<j)
      {
                temp=*(list+i);
                *(list+i)=*(list+j);
                *(list+j)=temp;
                i++;
                j--;
      }
}
基本思想：先把整个表倒序。例如a1-amb1-bn 翻转得到bn-b1am-a1再将b表，a表依次翻转即可。


测试代码：
#include <stdio.h>

void exchangelist(int *list,int m,int n);

void main()
{
      int list;
    int i;
      
      for (i=0;i<20;i++)
                list=i+1;
      exchangelist(list,12,8);
      printf("Exchange successfully!\n");
      for (i=0;i<20;i++)
                printf("%3d",list);
      printf("\n");
}

快乐阳光 发表于 2013-8-3 08:43:52

路过...........................................

天下无敌丑爸爸 发表于 2013-8-3 09:46:57

矮油，支持啊，搞算法的大神，你把小甲鱼拉着，我可以每天陪你一算！哈哈！

非常7十1 发表于 2013-8-3 09:47:40

路过，顶一下

ssyss501 发表于 2013-8-3 10:14:25

算法不是太了解

天下无敌丑爸爸 发表于 2013-8-3 12:23:19

要是能快点我就写楼上那个算法了，以前也看过，唉，为了完全摆脱这种逆序思维，真是麻烦，不知道楼主看看我这样的折叠然后进行加头加尾的方法有没有可能能够进一步的提高效率，而且我不要鱼币你给我点荣誉值哈，我要早点升到鱼油1.像楼主致敬，明天的算法帖子我要早点来了。
#include <iostream>
#define MIN(a,b)                a>b?b:a
#define MAX(a,b)        a>b?a:b
void sort(int* p,int m,int n);
void rush(int* p,int m,int n);
void addhead(int* p,int j,int k);
void addtail(int* p,int j,int k);
void display();
void main()
{       
int p={0};
for(int i=0;i<20;i++)
p=i+1;
for(int j=0;j<i;j++)
std::cout<<p<<std::ends;
std::cout<<std::endl;
sort(p,8,12);
for(j=0;j<i;j++)
std::cout<<p<<std::ends;
}
void sort(int* p,int m,int n)
{
rush(p,m,n);
if(m>n)
addhead(p,n,m);
else if(m<n)
addtail(p,n,m);
}
void rush(int* p,int m,int n)
{
int rep;
int a=MIN(m,n);
int b=MAX(m,n);
for(int i=0;i<a;i++)
{
rep=p;
p=p;
p=rep;
}
}
void addhead(int* p,int j,int k)
{
for(int q=j;q>0;q--)
{
int rep=p;
for(int i=k;i>0;i--)
{
        p=p;
}
p=rep;
}
}
void addtail(int* p,int j,int k)
{
for(int q=j-k;q>0;q--)
{
int rep=p;
for(int i=j-1;i>0;i--)
{
p=p;
}
p=rep;
}
}
思路：首先进行折叠，然后进行加尾，当m<n时进行加头。对于m=18，n=2。这样m n差距较大的时候我算法估计要快一点。

晨风吹过 发表于 2013-8-15 08:30:19

不错，学习了

330740120 发表于 2013-8-15 09:03:20

路过！~拿点分回家

qingtiancao 发表于 2013-8-15 09:30:20

我这都是哪天了，赶不上了

牡丹花下死做鬼 发表于 2013-8-16 15:19:18

qingtiancao 发表于 2013-8-15 09:30 static/image/common/back.gif
我这都是哪天了，赶不上了

只要你有思路就不怕晚 我想了半天没想出什么好的方法来 ~~~~(>_<)~~~~ {:5_100:}

风雪傲月3728 发表于 2014-7-21 13:04:29

只是路过，看看

繁空.星雨 发表于 2014-7-23 12:17:38

顶一下

14709722197 发表于 2014-7-23 14:27:56

唉跟不上

wangerwanger 发表于 2014-7-27 10:17:36

负责支持楼主！！

mumudontcry 发表于 2014-7-28 02:44:53

感谢楼主分享，突然发现：我适量给予评分
这样的话会导致拿分的多余讨论的

醉、爱 发表于 2014-7-29 22:53:26

Potato丶 发表于 2013-7-20 10:14
基本思想：先把整个表倒序。例如a1-amb1-bn 翻转得到bn-b1am-a1再将b表，a表依次翻转即可。




厉害。。。。

waliemiao 发表于 2015-10-7 14:00:54

厉害。。。。
页: [1]
查看完整版本: 算法一日一练 01