| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 654 人关注过本帖
标题:请大侠解释下这个算法
只看楼主 加入收藏
menghuann
Rank: 1
等 级:新手上路
帖 子:8
专家分:0
注 册:2010-1-13
结帖率:0
收藏
已结贴  问题点数:20 回复次数:5 
请大侠解释下这个算法
设计一个时间复杂度为O(n)的算法,实现将数组A[n]中所有元素循环右移k个位置
就是那个Reverse函数如何递归调用和为什么是to-from还加1不是from-to?不是n=from,k=to吗?
图片附件: 游客没有浏览图片的权限,请 登录注册
搜索更多相关主题的帖子: 元素 时间 
2010-12-30 23:24
诸葛修勤
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:11
帖 子:549
专家分:1955
注 册:2010-10-28
收藏
得分:20 
这个算法是左移  不是右移
至于下面的一系列的问题 主要是数组下标是从零开始的

#include <stdio.h>

void Reverse( int A[], int from, int to )
{
    int temp;//临时缓冲区
    for(int i=0; i<(to-from+1)/2; ++i )
    {
        temp = A[from+i];
        A[from+i] = A[to-i];
        A[to-i] = temp;
    }
    return;
}

void Converse(int A[], int n, int k)
{
    Reverse(A, 0, k-1);
    Reverse(A, k, n-1);
    Reverse(A, 0, n-1);
    return;
}

int main()
{
    int A[]={1, 2, 3, 4, 5, 6};
    int i;
    Converse(A, 6, 1);

    for(i=0; i<6; ++i)
    {
        printf("%d ", A[i]);
    }
    printf("\n");

    return 0;
}
2011-01-01 09:02
诸葛修勤
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:11
帖 子:549
专家分:1955
注 册:2010-10-28
收藏
得分:0 
这里 并没有用到递归

正如其函数的形式
算法分三步:
1。 选定从零下标开始的k个单元 进行前后调换位置
2。 选定剩下的n-k个单元 进行前后调换位置
3。 整体n个单元做一次前后位置的调换

完成上述3步则完成了循环左移懂k位的处理
2011-01-01 09:06
诸葛修勤
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:11
帖 子:549
专家分:1955
注 册:2010-10-28
收藏
得分:0 
知道左移 右移的就没有多大的分别啦
2011-01-01 09:09
menghuann
Rank: 1
等 级:新手上路
帖 子:8
专家分:0
注 册:2010-1-13
收藏
得分:0 
我还是有2个疑问:
1 由调用函数和被调用函数可以知道,n=from,k=to,i<(to-from+1),那么k-n不就小于0了吗?
2 Revrse(A,0,k-1)具体是什么意思?
2011-01-20 20:39
menghuann
Rank: 1
等 级:新手上路
帖 子:8
专家分:0
注 册:2010-1-13
收藏
得分:0 
难道大侠不上网???
2011-01-28 12:24
快速回复:请大侠解释下这个算法
数据加载中...
 
   



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

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