問題描述:
一個(gè)數(shù)組A中存有N(>0)個(gè)整數(shù)被因,在不允許使用另外數(shù)組的前提下赋兵,將每個(gè)整數(shù)循環(huán)向右移M(≥0)個(gè)位置嫉称,即將A中的數(shù)據(jù)由(A0A1 ?AN?1)變換為(AN?M?AN?1A0A1?AN?M?1)(最后M個(gè)數(shù)循環(huán)移至最前面的M個(gè)位置)罕伯。如果需要考慮程序移動(dòng)數(shù)據(jù)的次數(shù)盡量少凰荚,要如何設(shè)計(jì)移動(dòng)的方法燃观?
輸入格式:
每個(gè)輸入包含一個(gè)測(cè)試用例,第1行輸入N(1≤N≤100)和M(≥0)便瑟;第2行輸入N個(gè)整數(shù)缆毁,之間用空格分隔。
輸出格式:
在一行中輸出循環(huán)右移M位以后的整數(shù)序列到涂,之間用空格分隔脊框,序列結(jié)尾不能有多余空格颁督。
輸入樣例:
6 2
1 2 3 4 5 6
輸出樣例:
5 6 1 2 3 4
我的思路是將每個(gè)整數(shù)循環(huán)右移M個(gè)位置,然后將最后M個(gè)數(shù)移到前面的M個(gè)位置缚陷。
我一開始的實(shí)現(xiàn)沒有考慮到移動(dòng)次數(shù)最少适篙,暴力的實(shí)現(xiàn)。這樣很耗時(shí)箫爷,代碼量右大。下面的實(shí)現(xiàn)是partialy accepted.
#include <iostream>
using namespace std;
int main()
{
int numberCount, moveCount;
int number[200] = {0};
cin >> numberCount >> moveCount;
if (numberCount > 100 || numberCount < 1)
{
return -1;
}
for (int i = 0 ; i < numberCount ; i++)
{
cin >> number[i];
}
if (moveCount)
{
for (int i = numberCount - 1; i >= 0; i--)
{
number[i + moveCount] = number[i];
}
for (int i = 0; i <= moveCount - 1; i++)
{
number[i] = number[numberCount + i];
}
}
for (int i = 0 ; i < numberCount - 1 ; i++)
{
cout << number[i] << " ";
}
cout << number[numberCount - 1];
return 0;
}
另一種思路:我們?yōu)槭裁匆庉嬕苿?dòng)數(shù)組元素的代碼呢聂儒?我們關(guān)心的是輸出數(shù)組循環(huán)右移后的數(shù)組元素虎锚。因此無需移動(dòng)數(shù)組元素,根據(jù)移動(dòng)后的元素輸出樣例衩婚,直接按照某種方法輸出窜护。這個(gè)方法似乎違背了原題的本意,如何設(shè)計(jì)移動(dòng)的方法
#include <iostream>
using namespace std;
int main()
{
int res[200] = {0};
int m, n;
cin >> m >> n;
for (int i = 0; i < m; i++) {
cin >> res[i];
}
for (int i = 0; i < m; i++) {
cout << res[(m - (n % m) + i) % m]; //我們從測(cè)試數(shù)組的第四號(hào)位置開始遍歷
if (i != m - 1) {
cout << " ";
}
}
}