首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2010年计算机联考真题——一维数组循环左移

2010年计算机联考真题——一维数组循环左移

作者头像
AI那点小事
发布2020-04-20 15:51:00
4290
发布2020-04-20 15:51:00
举报
文章被收录于专栏:AI那点小事AI那点小事

前记


从七月份决定开始考研,中间由于听报告,回家复习数学和政治而耽误了一些时间。自己准备报考山东大学计算机技术的专硕,幸好是数学是考数学二,专业课也只有一门数据结构,这位我的复习节省了很多时间,不想数学一和统考的计算机基础综合的专业复习那么费劲。现在数据结构的复习完全是参照《王道考研系列——2018年数据结构考研复习指导》在复习。对于数据结构虽然到时候是手写算法,但是毕竟这是编程,对于算法能否正确实现并符合题目要求,只有跑程序才能看见。所以复习的同时,有也想利用好csdn博客来记录自己复习过程,故现在开始把指导书上的所有题与基础算法和数据结构利用博客来记录一下。

题目


设将n(n,1)个整数存放到一维数组R中,试设计一个在时间和空间两方面尽可能有效的算法,将R中保有的序列循环左移P(0﹤P﹤n)个位置,即将R中的数据由(X0 X1 ……Xn-1)变换为(Xp Xp+1 ……Xn-1 X0 X1 ……Xp-1)要求:

  (1)给出算法的基本设计思想。

  (2)根据设计思想,采用C或C++或JAVA语言表述算法,关键之处给出注释。

  (3)说明你所设计算法的时间复杂度和空间复杂度


思路


对于这个问题:可以把问题转化为把数组的前p个数与后n-p个数进行位置互换。即把后n-p个数整体放到前p个数的前面即可。


代码

#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;

//把下标在[left,right]的数进行逆置 
bool Reverse(int* A ,int left , int right , int size)
{
    if(left >= right || right >= size)
        return false;
    int mid = (left+right)/2;
    for(int i = 0 ; i < mid - left ; i++){
        A[i+left] += A[right-i];
        A[right-i] = A[i+left] - A[right-i];
        A[i+left] -= A[right-i];
    }
    return true;
}

//把前m个数与后n个数互换位置 
void Exchange(int* A ,int m, int n ,int size) 
{
    Reverse(A,0,m+n-1,size);        //下标0~m+n-1的数逆置
    Reverse(A,0,n-1,size);          //下标0~n-1的数逆置
    Reverse(A,n,m+n-1,size);        //下标n~m+n-1的数逆置 
}

int main()
{
    int a[7];
    for(int i = 0 ; i < 7 ; i++){
        a[i] = i+1;
    } 

    cout<<"对换前"<<endl;
    for(int i = 0 ; i< 7 ; i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;

    Exchange(a ,3,4,7);
    cout<<"对换后"<<endl;
    for(int i = 0 ; i< 7 ; i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;

    return 0;
}
这里写图片描述
这里写图片描述
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前记
  • 题目
    • 思路
      • 代码
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档