主题：貌似不会做~~~~~高手在否!??
1259121
[专家分：0] 发布于 2006-10-31 12:56:00
1.设计一个算法，将数组 A(0:n-1) 中的元素循环右移 k 位，要求只用一个元素的附加空间，元素移动或交换次数为O(n)。
2.求下列广义表运算的结果：
1、Head[((a,b),(c,d))]
2、Tail[((a,b),(c,d))]
3、Head[Tail[((a,b),(c,d))]]
4、Tail[Head[((a,b),(c,d))]]
5、Head[Tail[Head [((a,b),(c,d))]]]
6、Tail[Head[Tail [((a,b),(c,d))]]]
3.利用 Head 和 Tail 运算将下列广义表中的原子 c 取出来：
1、L1=(a,b, c,d)
2、L2=((a,b),(c,d))
3、L3=(((a),(b), (c),(d)))
4、L4=(a,(b),((c)),(((d))))
5、L5=((((a))),((b)),(c),d)
6、L6=((((a),b),c),d)
7、L7=(a,(b,(c,(d))))
8、L8=(a,(b,(c),d))
万望帮忙~~~谢谢!!
shyalb@163.com
回复列表 （共8个回复）
沙发
majianan [专家分：1100] 发布于 2006-10-31 14:15:00
第一题,假如右移5位,那数组中最后一会向右移5位,移动到哪里去了?
说明一下啊.移动到a[4]处？
板凳
1259121 [专家分：0] 发布于 2006-10-31 15:25:00
就是把整个数列看作一个循环,最后一个数的右面是第一个数~
3 楼
max810511 [专家分：170] 发布于 2006-11-02 09:15:00
void move(DataType A[],int n,int k)
{
int i; DataType temp; /*temp为附加的一个空间*/
for(i=0,i<n;i++)
{
temp=A[i];
A[i]=A[(i+k)%n];
A[(i+k)%n]=temp;
}
}
4 楼
leolhc [专家分：430] 发布于 2006-11-02 10:18:00
3楼的解答是错误的
例如
0 1 2 3 4 5
右移2位，运行后结果是
0 1 4 5 2 3
而
0 1
右移1位，运行后结果还是
0 1
第一题的答案可见我在下面的回复
http://www.programfan.com/club/showbbs.asp?id=199441
只是是用delphi实现的，楼主得自己消化下了
第2、3题的答案由定义可很容易的求得，自己翻书就可以了，特别要注意的是括号的问题。
5 楼
max810511 [专家分：170] 发布于 2006-11-02 11:59:00
Sorry,比较匆忙，改了一下。
void move(DataType A[],int n,int k)
{
int i; DataType temp; /*temp为附加的一个空间*/
for(i=0,i<n-k;i++)
{
temp=A[i];
A[i]=A[(i+n-k)%n];
A[(i+n-k)%n]=temp;
}
}
6 楼
leolhc [专家分：430] 发布于 2006-11-02 16:39:00
5楼好像还是不对哦
0 1 2 3
右移3位，n-k==1，运行结果是
1 0 2 3
即使把i+n-k改为原来的i+k，变成
3 1 2 0
也不对。
正确应该是
1 2 3 0
希望你再接再厉，写个简单正确的出来，我对我那个需要求公约数的觉得很繁。
7 楼
xiaoou333 [专家分：20] 发布于 2006-11-03 01:32:00
#include <cstdlib>
#include <iostream>
using namespace std;
int a[100];
int gcd(int a,int b);
int main(int argc, char *argv[])
{
int n,k,temp;
while(cin>>n>>k)
{
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=1;i<=gcd(n,k);i++)
{
temp=a[n-(gcd(n,k)-i)-1];
for(int j=n-1-(gcd(n,k)-i);j>=i-1+gcd(n,k);j-=gcd(n,k))
a[j]=a[j-gcd(n,k)];
a[i-1]=temp;
}
for(int i=0;i<n;i++)
cout<<a[i]<<' ';
cout<<'\n';
}
return 0;
}
int gcd(int a,int b)
{
if(b==0)return a;
return gcd(b,a%b);
}
8 楼
max810511 [专家分：170] 发布于 2006-11-03 08:43:00
不好意思，加上一句。
void move(DataType A[],int n,int k)
{
int i,times; DataType temp;
times=k < n/2 ? n-k : k ;
for(i=0;i<times;i++)
{
temp=A[i];
A[i]=A[(i+n-k)%n];
A[(i+n-k)%n]=temp;
}
}
我来回复
您所在位置：