算法作业1-右移数组

每天属于自己的时间，就是慢慢的刷题的时候，啥也不用想，沉浸在写出最佳程序的过程中，沉浸在自己阅读大牛代码，提升自我的过程中，那种满足感，真的很让人享受<.>

题目:右移数组

已知一个长度为 n 的数组和一个正整数 k，并且最多只能使用一个用于交换数 组元素的附加空间单元，试设计算法得到原数组循环右移 k 次的结果并分析算法的时间复杂度。

解题思路：

方法：

在自己尝试的过程中，发现了一个很有趣的规律，
例如

arr=1 2 3 4 5 n=5,k=2

显然右移两位以后的数组为

4 5 1 2 3

而该数组的逆序为

3 2 1 5 4

恰好是123 45子数组的逆序
由此，该算法就很容易了

#include "stdafx.h"
#include <string>
#include <assert.h>
#include <iostream>
using namespace std;

void nixu(char* arr, int start, int end) {//arr为数组，n为数组长度，k为右移位数
										 
	char tmp;
	while (start < end)
	{
		tmp = arr[start];
		arr[start] = arr[end];
		arr[end] = tmp;
		start++;
		end--;
	}
}

int main() {
	int n = 0, k = 0, flag = 0;
	cout << "请输入数组长度:";
	cin >> n;
	char *arr = new char[n];
	cout << endl;
	cout << "请输入数组:";
	while (flag == 0)
	{
		cin >> arr;
		if (strlen(arr) == n)
		{
			flag = 1;
		}
		else
		{
			cout << "请重新输入数组，因为数组长度不为n"<<endl;
		}
	}
	cout << endl;
	cout << "请输入右移次数:";
	cin >> k;
	cout << endl;
	nixu(arr, 0, n - k - 1);
	nixu(arr, n - k, n - 1);
	nixu(arr, 0, n - 1);
	cout << arr;
	return 0;
}