精华内容
下载资源
问答
  • 循环左移pos位,即将数组中的每个元素下标向前移动pos位,其中前面没有位置的数组元素循环移位到数组的末尾 如下图,长度为4的数组循环左移一位,即a1-a3分别移位到数组的第1-3位,而a0则移位到第4位 而我们今天要...

    数组元素循环左移

    理论

    循环左移pos位,即将数组中的每个元素下标向前移动pos位,其中前面没有位置的数组元素循环移位到数组的末尾
    如下图,长度为4的数组循环左移一位,即a1-a3分别移位到数组的第1-3位,而a0则移位到第4位
    在这里插入图片描述
    而我们今天要谈的是【将一维数组中的元素循环左移P个元素】
    题目大致如下:设将n(n>1)个整数存放到一维数组R中,设计一个算法,将R中的序列循环左移P(0<P<n)个位置,即将R中的数据由{X0,X1,…,Xn-1}变换为{Xp,Xp+1,…,Xn-1,X0,X1,…,Xp-1}
    这里就要用到一个算法结论,即
    从{X0,X1,…,Xn-1}变换为{Xp,Xp+1,…,Xn-1,X0,X1,…,Xp-1}需要3步:
    (1){X0,X1,…,Xp-1}数组前部分逆转位置
    (2){Xp,Xp+1,…,Xlen-1}数组后一部分逆转位置
    (3){X0,X1,…,Xlen-1}整个数组逆转位置
    从而我们可以将这种思想归纳为函数cycleLeft(int arr[],int len,int pos)

    鉴于逆转的操作比较独立且语句不少,因而我们单独为其构造一个reverse(int arr[],int begin,int end)逆转函数
    逆转数组元素如下图所示,需要引入一个过渡变量temp暂存要转换的其中一个元素
    在这里插入图片描述

    代码

    //数组元素循环左移 
    #include <iostream>
    #include <cmath>
    #include <cstring>
    using namespace std;
    
    //逆置代码
    void reverse(int arr[],int begin,int end){
    	int i,j;
    	for(i = begin,j = end;i < j;i++,j--){
    		int temp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = temp;
    	}
    }
    //循环左移代码,arr为操作数组,len为数组长度,pos为为移动位数 
    void cycleLeft(int arr[],int len,int pos){
    	reverse(arr,0,pos-1);
    	reverse(arr,pos,len-1);
    	reverse(arr,0,len-1);
    }
    int main(){
    	int len,arr[1010];
    	cout<<"请输入数组长度与数据:"<<endl;
    	cin>>len;
    	for(int i=0;i<len;i++){
    		cin>>arr[i];
    	}
    	cout<<"循环左移之前的数组为:";
    	for(int i=0;i<len-1;i++){
    		cout<<arr[i]<<" ";
    	}
    	cout<<arr[len-1]<<endl;
    	
    	cout<<"请输入循环左移的位数:";
    	int CLnum;
    	cin>>CLnum;
    	cycleLeft(arr,len,CLnum);
    	
    	cout<<"循环左移之后的数组为:";
    	for(int i=0;i<len-1;i++){
    		cout<<arr[i]<<" ";
    	}
    	cout<<arr[len-1]<<endl;
    	return 0;
    }
    

    代码输出

    在这里插入图片描述

    展开全文
  • 文章转载自TOMORROW 星辰,原文链接:数组循环左移最优算法:逆置算法 设将 n 个整数存放到一维数组 R 中。试设计一个在时间和空间两方面都尽可能高效的算法,将 R 中元素序列循环左移 p 个位置。 该问题一个...

    文章转载自TOMORROW 星辰,原文链接:数组循环左移最优算法:逆置算法

    设将 n 个整数存放到一维数组 R 中。试设计一个在时间和空间两方面都尽可能高效的算法,将 R 中的元素序列循环左移 p 个位置。

    该问题的一个最优解为逆序算法。具体算法设计思路、时间复杂度与空间复杂度分析及算法源码(C 语言)如下。

    算法设计

    • 首先,将数组分为两部分 a、b,a 表示前 p 个元素,b 代表剩下的元素;
    • 那么原问题就可以看作是:将数组ab转换成 ba
    • 然后,将数组 R 中的 a、b 分别逆置得到 a^{-1}b^{-1}
    • 然后对 a^{-1}b^{-1}整体逆置就可以得到(a^{-1}b^{-1})^{-1}=ba

    举个例子:

    将 abcdefg 循环左移 3 位:

    • 将 abcdefg 分成 abc、defg 两部分;
    • 然后将两部分分别逆置然后组合得到 cba gfed;
    • 再将 cba gfed 整体逆置就可以得到 defgabc;
    • 这样就完成了将 abcdefg 循环左移 3 位;

    算法源码实现

    /*数组循环左移——逆置算法*/
    void reverse(int R[], int from, int to )
    {
    	int i ,temp ;
    	for(i=0; i<(to-from+1)/2; i++)
    	{
    		temp = R[from+i];
    		R[from+i] = R[to-i];
    		R[to-i] = temp;
    	}
    }
    
    void shift(int R[], int n, int p )
    {
    	reverse(R, 0, p-1);
    	reverse(R, p, n-1);
    	reverse(R, 0, n-1);
    }

    复杂度分析

    时间复杂度:三个 reverse 函数的时间复杂度分别是 O(p/2)、O((n-p)/2)、O(n/2),所以算法时间复杂度为 O(n)。

    空间复杂度:而空间复杂度就是 O(1)

     

    【另外非最优:时间换空间算法】

    借助辅助数组来解决问题:

    算法思想:

    • 借助一个大小为 p 的辅助数组 S,将数组 R 中的前 p 个元素一次暂存于 S 中;
    • 然后将 R 中剩余的其他元素左移 p 位;
    • 再将数组 S 中的元素一次存回 R 中的后续位置;

    时间复杂度和最优解的一样,都是 O(n);

    但是由于使用了辅助数组,所以空间复杂度为 O(p)。

    展开全文
  • 课程设计题目:用 Reverse 实现时间复杂度为 O(n)O(n)O(n) 数组循环左移算法 一、问题描述 设计一个时间复杂度为 O(n)O(n)O(n) 算法,实现将数组 A[n] 中所有元素循环左移 kkk 个位置。 详见王红梅等编著《数据...

    课程设计题目:用 Reverse 实现时间复杂度为 O(n)O(n) 数组循环左移算法

    一、问题描述

    设计一个时间复杂度为 O(n)O(n) 的算法,实现将数组 A[n] 中所有元素循环左移 kk 个位置。

    详见王红梅等编著的《数据结构(C++版)(第2版)》P53页习题5(1)。

    二、基本要求

    1. 实现将数组 A[n] 中所有元素循环左移 kk 个位置。

    2. 时间复杂度为 O(n)O(n)

    三、概要设计

    1. 算法的设计

    算法思路参考王红梅等编著的《数据结构(C++版)(第2版)》P16页思想火花,出自BW Kernighan和PJ Plauger于1981年发表的著作Software tools in Pascal

    1. 设计reverse(first, last)函数,用于实现反转从firstlast(不含)之间的元素;

    2. 通过3次reverse实现将数组 A[n] 中所有元素循环左移 kk 个位置:

      reverse(a, a + k)

      reverse(a + k, a + n)

      reverse(a, a + n)

    四、详细设计

    1. 设计每个函数

    void Reverse(int *first, int *last)
    {
        last--;
        for (int temp; first < last; first++, last--)
            temp = *first, *first = *last, *last = temp;
    }
    

    2. 设计主函数

    int main()
    {
        reverse(a, a + k);
        reverse(a + k, a + n);
        reverse(a, a + n);
    }
    

    五、运行与测试

    1. 测试环境

    运行环境:Windows 20H2, i7-9750H @ 2.60GHz, 16GB RAM

    编译器:gcc version 8.1.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project)

    编译命令:-g

    运行终端:cmd

    2. 在调试程序的过程中遇到的问题与解决方案

    暂未发现异常。

    3. 设计的测试数据与测试结果

    测试3次。输入k,然后生成一个随机数组并输出,数组所有元素循环左移 kk 个位置后再输出。

    4. 程序清单及运行结果

    4.1 A[n] 为整型数组

    程序清单如下。

    // ex1_2.cpp
    
    /*
     * 1. 编写程序:课本p53页习题5(1),先做整数,然后改用模板函数做并测试。
     * 课本p53页习题5(1):设计一个时间复杂度为 O(n) 的算法,实现将数组 A[n] 中所有元素循环左移 k 个位置。
     * 模板
     */
    
    #include <iostream>
    #include <ctime>
    using namespace std;
    
    template <typename T>
    void Reverse(T *first, T *last)
    {
        last--;
        for (T temp; first < last; first++, last--)
            temp = *first, *first = *last, *last = temp;
    }
    
    int main()
    {
        srand(time(NULL));
    
        int n = 10, k;
        cout << "Please input k(0 < k < 10): ";
        cin >> k;
    
        int A[n];
        for (int i = 0; i < n; i++)
            cout << (A[i] = rand()) << " ";
        cout << endl;
    
        Reverse(A, A + k);
        Reverse(A + k, A + n);
        Reverse(A, A + n);
    
        for (int i = 0; i < n; i++)
            cout << A[i] << " ";
        cout << endl;
    
        double B[n];
        for (int i = 0; i < n; i++)
            cout << (B[i] = (double)rand() / (rand() + 1)) << " ";
        cout << endl;
    
        Reverse(B, B + k);
        Reverse(B + k, B + n);
        Reverse(B, B + n);
    
        for (int i = 0; i < n; i++)
            cout << B[i] << " ";
        cout << endl;
    
        return 0;
    }
    

    第1次测试(符合预期)

    D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1
    Please input k(0 < k < 10): 3
    31255 22925 30731 23452 21176 11048 16126 26806 17875 16867
    23452 21176 11048 16126 26806 17875 16867 31255 22925 30731

    第2次测试(符合预期)

    D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1
    Please input k(0 < k < 10): 4
    31297 31583 821 8595 24193 29328 23820 21519 3149 2478
    24193 29328 23820 21519 3149 2478 31297 31583 821 8595

    第3次测试(符合预期)

    D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1
    Please input k(0 < k < 10): 5
    31310 9040 6742 6545 32684 12267 3502 9810 3660 10654
    12267 3502 9810 3660 10654 31310 9040 6742 6545 32684

    4.2 模板

    #include <iostream>
    #include <ctime>
    using namespace std;
    
    template <typename T>
    void Reverse(T *first, T *last)
    {
        last--;
        for (T temp; first < last; first++, last--)
            temp = *first, *first = *last, *last = temp;
    }
    
    int main()
    {
        srand(time(NULL));
    
        int n = 10, k;
        cout << "Please input k(0 < k < 10): ";
        cin >> k;
    
        int A[n];
        for (int i = 0; i < n; i++)
            cout << (A[i] = rand()) << " ";
        cout << endl;
    
        Reverse(A, A + k);
        Reverse(A + k, A + n);
        Reverse(A, A + n);
    
        for (int i = 0; i < n; i++)
            cout << A[i] << " ";
        cout << endl;
    
        double B[n];
        for (int i = 0; i < n; i++)
            cout << (B[i] = (double)rand() / (rand() + 1)) << " ";
        cout << endl;
    
        Reverse(B, B + k);
        Reverse(B + k, B + n);
        Reverse(B, B + n);
    
        for (int i = 0; i < n; i++)
            cout << B[i] << " ";
        cout << endl;
    
        return 0;
    }
    

    第1次测试(符合预期)

    D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1_2
    Please input k(0 < k < 10): 3
    31607 4105 26750 850 21038 9151 24591 5572 31655 8236
    850 21038 9151 24591 5572 31655 8236 31607 4105 26750
    0.551057 2.53344 0.209033 6.9253 0.0571197 1.1675 53.6444 0.791821 0.250341 1.0277
    6.9253 0.0571197 1.1675 53.6444 0.791821 0.250341 1.0277 0.551057 2.53344 0.209033

    第2次测试(符合预期)

    D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1_2
    Please input k(0 < k < 10): 4
    31624 25079 17767 22863 7075 28785 7385 23704 15909 10263
    7075 28785 7385 23704 15909 10263 31624 25079 17767 22863
    0.511611 0.172095 1.52812 1.01504 0.720147 9.04 10.3216 0.00956241 2.05172 0.394671
    0.720147 9.04 10.3216 0.00956241 2.05172 0.394671 0.511611 0.172095 1.52812 1.01504

    第3次测试(符合预期)

    D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1_2
    Please input k(0 < k < 10): 5
    31653 23511 14704 10057 1602 31357 2629 30126 673 20467
    31357 2629 30126 673 20467 31653 23511 14704 10057 1602
    0.4426 0.60074 5.66135 0.316398 0.906047 2.21183 135.865 0.0243682 0.37898 0.211203
    2.21183 135.865 0.0243682 0.37898 0.211203 0.4426 0.60074 5.66135 0.316398 0.906047

    六、总结与心得

    算法之美,妙不可言!

    七、参考资料

    1. 王红梅, 胡明, 王涛. 数据结构 (C++ 版)[M]. 清华大学出版社, 2005.

    2. Kernighan B W, Plauger P J. Software tools in Pascal[J]. 1981.

    展开全文
  • 数组的循环左移

    2020-02-18 10:55:13
    试设计一个在时间和空间两方面都尽可能高效的算法,将R中保存序列循环左移p(0<p<n)个位置,即将R中数据由(x0, x1…, xn-1)变换为(xp,xp+1,…,xn-1,x0,x1,…,xp-1)。 输入 多组数据,每组数据...

    描述

     

    设将n(n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法,将R中保存的序列循环左移p(0<p<n)个位置,即将R中的数据由(x0, x1…, xn-1)变换为(xp,xp+1,…,xn-1,x0,x1,…,xp-1)。

    输入

    多组数据,每组数据有三行。第一行为一个整数n,代表数组R中有n个元素。第二行为数组R中的n个元素(元素之间用空格分隔)。第三行为一个整数p,代表将R中的序列循环左移p个位置。当n等于0时,输入结束。

    输出

    每组数据输出一行,为移动后的数组R中所存放的序列。每两个数之间用空格分隔。 输入样例

    输入样例 1 

    5
    1 2 3 4 5
    1
    6
    -1 2 3 2 4 3
    3
    0

    输出样例 1

    2 3 4 5 1
    2 4 3 -1 2 3
    #include <iostream>
    using namespace std;
    
    void MoveLeft(int a[],int n,int m)
    {
    	int i;int b[n];
    	for(i=0;i<n;i++)
    		if(i+m<n)
    			b[i]=a[i+m];
    		else b[i]=a[(i+m)%n];
    	for(i=0;i<n;i++)
    	{
    		cout<<b[i];
    		if(i!=n-1)cout<<" ";//?
    	}	
    	cout<<endl;
    
    }
    
    int main()
    {
    	int n; 
    	cin>>n;
    	while(n!=0)
    	{
    		int a[n];int i;int m;
    		for(i=0;i<n;i++)
    			cin>>a[i];
    		cin>>m; 
    		MoveLeft(a,n,m);
    		cin>>n;
    	 } 
     }

     

    展开全文
  • 简单算法——一维数组的循环左移

    千次阅读 2017-09-16 16:28:08
    给定一个有n个元素的数组,使其整体左移m位(m#include #include #include <stdlib.h>int main(){ int m=0,n=0,i=0,e=0; printf("请输入序列长度:"); scanf("%d",&n); //定义数组并赋值 int *arr=(int*)...
  • 程序要求: 动态输入数组长度(n)和要循环左移的次数§,如次数大于或等于数组长度程序自动结束;否则用户继续依次输入n个...将数组的前P个元素反转,反转后的数组a[n]是: {a(p-1),a(p-2),…a1,a0,a§,a(p+1),…a(n-1)}
  • 数组元素循环左移

    千次阅读 2017-07-03 21:26:46
    设将n(n>1)个整数存放到一维数组R中,设计一个算法,将R中序列循环左移P(0 分析: 要实现R中序列循环左移P个位置,只需先将R中前P个元素逆置,再将剩下元素逆置,最后将R中所有元素再整体做一次逆置操作...
  • 问题描述:对于给定的数组循环左移p个元素 说明:对于这个问题,我想了有三种方法。(当然,还参考了资料),把它们简要实现出 来了。现简要叙述如下: MoveLeft1:这种算法的思路是,将第一个元素暂时...
  • 试设计一个在时间和空间两方面都尽可能高效的算法,将R中保存序列循环左移p(0<p<n)个位置,即将R中数据由(x0, x1…, xn-1)变换为(xp,xp+1,…,xn-1,x0,x1,…,xp-1)。 输入 多组数据,每组数据有...
  • 数组循环左移P位算法

    2017-09-07 14:16:47
    设计一个代码将R中序列循环左移P(0),即将R中数据由 {X0,X1,……Xn-1}变换为{Xp,Xp+1,……,Xn-1,X0,X1,……,Xp-1} 分析:将前P个元素逆置,再将剩下元素逆置,最后将所有元素逆置
  • 说白了数组的左移就是一个交换的过程,既然能做到不用额外的空间交换数据,那做数组的左移也是可以做的。 先说说不用额外的空间实现两个数据的交换: int a=10; int b=15; a = a + b; b = a - b; a = a -
  • n个整数存放到一位数组R中,将R中元素循环左移p个位置。 (1)算法的基本设计思想 创建另外一个数组_R,将排序后元素放在_R中,然后利用_R更新R。 时空复杂度都贼鸡儿丢人。 (2)代码如下 #include &...
  • 数组循环左移

    2020-05-06 17:29:56
    数组循环左移 题目:将 n 个整数存放到一维数组 R 中。设计一个尽可能高效的算法,将 R 中保存序列循环左 移 p 个(0<p<n )位置,即将 R 中数据由(????0,????1,????2,…,????????−1) 变换为 (????????,?...
  • 数组循环左移问题

    2021-02-27 21:17:51
    数组循环左移问题三种解法问题/题干 描述解法1解法2解法3 问题/题干 描述 将一个具有n个元素的数组向左循环移动i个位置。 这只一个很实用问题,很多应用程序会调用这个问题的算法,例如在文本编辑器中移动行...
  • 习题2.2 数组循环左移 颠倒交换法 算法描述:循环左移k位, 把前面 0 到 k-1位置数字首尾交换, 把 k 到 len-1位置首尾交换, 再把 0 到 len-1下标位置首位交换
  • 数组循环左移

    2020-03-12 15:17:28
    试设计一个在时间和空间两方面都尽可能高效的算法,将R中保存序列循环左移p (0<p<n) 个位置,即将R中数据序列由(x0, x1,……,xn-1)变换为(xp,xp+1,……,xn-1,x0,x1,……,xp-1)。 在没学算法之前...
  • 对于一个任意长度为len的数组A,使其循环左移P个元素。如数组{1,2,3,4,5,6,7},左移3个元素即变为{4,5,6,7,1,2,3}。 实现算法 方法一 对前3个元素完全转置,变为{3,2,1,4,5,6,7} 对后4个元素完全转置,变为{3,2...
  • 数组循环左移p个位置

    2018-03-25 11:54:44
    算法】将一维数组arr中元素循环左移p个位置 原创 2017年05月03日 23:35:35 &lt;ul class="article_tags...
  • 试设计一个在时间和空间两方面尽可能高效算,将R中保存序列循环左移动p个位置,即将R中数据由(x0,x1,x2,…xn-1)变换为(xp,xp+1,…xn-1,x0,…xp)。要求: 给出算法的基本设计思想 说明算法的时间复杂度和空间...
  • 循环左移/右移k位 可以使用三段反转算法,但是需要注意是,在使用前需要k%n n为数组长度
  • 1)个整数存放到一维数组R中,设计一个算法,将R中序列循环左移P(0<P<n)个位置,即将R中数据由{x0,x2,…,xn-1}变换为{xP,xP+1,…,xn-1,x0,x1,…,xP-1}。 算法分析: 可以先将R中前P个元素逆置,再将剩下...
  • 数据结构习题(数组循环左移

    千次阅读 2019-04-11 23:58:15
    将R中保存序列循环左移p(0 < p < n)个位置,即将R中数据由(X0,X1,…,Xn-1`)变换为(Xp,Xp+1,…,Xn-1,X0,X1,…,Xp-1)。要求: 1)给出算法的基本设计思想 2)根据设计思想,采用C或++或Java语言描述算法,...
  • 对于一个任意长度为len的数组A,使其循环左移P个元素。如数组{1,2,3,4,5,6,7},左移3个元素即变为{4,5,6,7,1,2,3}。 实现算法 方法一 对前3个元素完全转置,变为{3,2,1,4,5,6,7} 对后4个元素完全转置,变为{3,2,1,7,6...
  • 试设计一个在时间和空间两方面都尽可能高效的算法,将RRR中保存序列循环左移P(0&amp;amp;amp;lt;P&amp;amp;amp;lt;n)P(0&amp;amp;amp;lt;P&amp;amp;amp;lt;n)P(0&amp;amp;lt;P&

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 212
精华内容 84
关键字:

数组的循环左移算法