[编程题]怪异的洗牌
- 热度指数：3995 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
对于一副扑克牌，我们有多种不同的洗牌方式。一种方法是从中间某个位置分成两半，然后相交换，我们称之为移位（shift）。比如原来的次序是123456，从第4个位置交换，结果就是561234。这个方式其实就是数组的循环移位，为了多次进行这个操作，必须使用一种尽可能快的方法来编程实现。在本题目中，还引入另外一种洗牌方式，就是把前一半（如果总数是奇数，就是(n-1)/2）牌翻转过来，这种操作称之为翻转（flip）。在前面shift操作的结果上进行flip，结果就是165234。当然，如果是实际的扑克牌，直接翻转会造成正反面混在一起的，我们就不管那么多了。
给定n张牌，初始次序为从1到n，经过若干次的shift和flip操作后，结果会是什么样？
输入描述:
输入包括多组测试数据，每组数据的第一行包括两个数 n和k。n表示牌的数目，1<n<1000，k表示下面要进行的操作数量。随后的k行，每行一个整数x，1<=x<=n，表示从第几个位置开始移位。在每一次shift操作后都接一个flip操作。
输出描述:
对于输入的每组数据，计算经过给定的k次shift和flip操作后，各个位置的数值。并按次序在一行上输出所有牌张的值，每个数值（不包括最后一个）后面有一个空格。
示例1
输入
6 1 4 0 0
输出
1 6 5 2 3 4
来一波骚操作，拼命移位就完事了；
#include<bits/stdc++.h>
using namespace std;
int n,k,x,a[1005];
int main() {
#ifdef ONLINE_JUDGE
#else
freopen("input.txt","r",stdin);
#endif
while(cin>>n>>k&&!cin.eof()) {
for(int i=0; i<n; i++) a[i]=i+1;
while(k--) {
cin>>x;
reverse(a,a+x);
reverse(a+x,a+n);
reverse(a,a+n);
n&1?reverse(a,a+(n-1)/2):reverse(a,a+n/2);
}
for(int i=0; i<n; i++) i==0?cout<<a[i]:cout<<" "<<a[i];
cout<<endl;
}
return 0;
}
发表于 2019-02-16 11:35:00
回复(1)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v;
void shift(int x) {
reverse(v.begin(),v.begin()+x);
reverse(v.begin()+x,v.end());
reverse(v.begin(),v.end());
}
void flip() {
int middle=-1;
if(v.size()%2==0) {
middle=v.size()/2;
} else {
middle=(v.size()-1)/2;
}
reverse(v.begin(),v.begin()+middle);
}
int main() {
int n,k,pos;
while(scanf("%d%d",&n,&k)!=EOF) {
v.clear();
for(int i=0;i<n;i++) {
v.push_back(i+1);
}
while(k--) {
scanf("%d",&pos);
shift(pos);
flip();
}
for(int i=0;i<v.size();i++) {
if(i!=v.size()-1) {
printf("%d ",v[i]);
} else {
printf("%d\n",v[i]);
}
}
}
return 0;
}
发表于 2018-03-17 18:17:01
回复(0)
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[1005];
int main(){
int n,k,x,i;
//freopen("input.txt","r",stdin);
while(scanf("%d%d",&n,&k)!=EOF&&n){
for(i=0;i<n;i++) a[i]=i+1;
while(k--){
scanf("%d",&x),x%=n;
rotate(a,a+x,a+n);
reverse(a,a+n/2);
}
for(i=0;i<n;i++) printf("%d ",a[i]);
printf("\n");
}
}
发表于 2017-11-10 20:04:44
回复(2)
主要运用vector和reverse，字符数组翻过来调过去，整一整就通了哈哈^_^
#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int main() {
int n,k,pos,m,x;
while(scanf("%d %d",&n,&k)!=EOF&&n!=0)
{
v.clear();
for(int i=0;i<n;i++)
{
v.push_back(i+1);
}
m=v.size();
while(k--)
{
scanf("%d",&x);
reverse(v.begin(),v.begin()+x);//移位，注意x为长度不是下标
reverse(v.begin()+x,v.end());//x为下标
reverse(v.begin(),v.end());
m%2==0? m/=2:m=(m-1)/2;//翻转
reverse(v.begin(),v.begin()+m);
m=v.size();
}
for(int i=0;i<v.size();i++)
{
if(i!=v.size()-1)
printf("%d ",v[i]);
else
printf("%d\n",v[i]);
}
}
return 0;
}
发表于 2020-04-07 15:27:46
回复(0)
纯c实现,不借助函数库,重点找好需要动的起始位置 #include<stdio.h>
#include<stdio.h>
int main()
{
int n,m,k,i,j,t,a[1000];
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)//数组赋值
a[i]=i+1;
while(m--)//操作次数
{
scanf("%d",&k);//操作位置
int w=n-k;//1.循环前移 从最后一个数开始
while(w--)//前移的次数
{
for(j=n-1;j>0;j--)
{//交换
t=a[j];a[j]=a[j-1];a[j-1]=t;
}
}
//2.前面一半倒序
int w1=n/2-1;//要交换的最后一个数值
for(i=0;i<(n/4);i++)//交换的次数
{//交换
t=a[i];a[i]=a[w1];a[w1]=t;
w1--;
}
}
for(i=0;i<n;i++)
printf("%d ",a[i]);
}
编辑于 2020-03-27 22:58:44
回复(1)
多个reverse()函数，也可以用rotate(first,middle,end)函数直接实现移位；
#include<iostream>
(720)#include<string>
#include<algorithm>
using namespace std;
const int N = 1000;
int a[N];
void Initial()
{
for (int i = 0; i < N; i++)
a[i] = i + 1;
}
void reversessss(int length,int n)
{
reverse(a,a+n); //引入头文件
reverse(a + n, a + length);
reverse(a, a + length);
}
int main()
{
int k, n;
int x;
while (cin >> n >> k)
{
Initial();
for (int i = 0; i < k; i++)
{
cin >> x; //location
reversessss(n, x);
reverse(a, a + n / 2);
}
for (int i = 0; i < n; i++)
if (i == 0) cout << a[i];
else cout << " " << a[i];
}
}
发表于 2020-03-18 11:26:00
回复(0)
#include <bits/stdc++.h>
using namespace std;
struct node{
int number;
node* next;
node* previous;
};
node* create(int n){
node* head;
node* pre;
node* p;
head=new node;
head->next=NULL;
head->previous=NULL;
pre=head;
for(int i=1;i<=n;i++){
p=new node;
p->number=i;
p->next=NULL;
p->previous=pre;
pre->next=p;
pre=p;
}
return head;
}
void shift(node* head,int p,int n){
if(p==n) return;
node* cur;
//切点
cur=head->next;
for(int i=0;i<p;i++){
cur=cur->next;
}
// 尾节点
node* tail;
tail=head;
while(tail->next!=NULL){
tail=tail->next;
}
//移位
cur->previous->next=NULL;
cur->previous=head;
tail->next=head->next;
head->next->previous=tail;
head->next=cur;
}
void flip(node* head, int n){
node* tail;//中间节点
node* cur;
cur=head->next;
tail=head;
if(n%2==0){
for(int i=0;i<n/2;i++){
tail=tail->next;
}
}else{
for(int i=0;i<(n-1)/2;i++){
tail=tail->next;
}
}
//不用考虑奇偶
int swap=0;
for(int i=0;i<n/2/2;i++){
swap=cur->number;
cur->number=tail->number;
tail->number=swap;
tail=tail->previous;
cur=cur->next;
}
}
int main(){
int n;
int k;
int p;
node* head;
while(cin>>n>>k){
if(n==0) return 0;
//创建链表
head=create(n);
while(k--){
cin>>p;
//移位
shift(head,p,n);
//翻转
flip(head,n);
}
//输出
node* current=head->next;
for(int i=0;i<n-1;i++){
cout<<current->number<<" ";
current=current->next;
}
cout<<current->number<<endl;
//释放空间
node* del;
node* del_next;
del=head->next;
del_next=del->next;
for(int i=0;i<n;i++){
delete(del);
del=del_next;
if(del_next!=NULL)
del_next=del_next->next;
}
}
return 0;
}
发表于 2020-03-07 14:06:27
回复(0)
本来有一种提升效率的方法，那就是shift操作的时候压根就不移动任何元素，设置一个变量表示起点的位置，只改动这个变量就相当于完成了shift操作，数组用循环数组表示
不过简单粗暴的做一样可以通过，我就偷懒了
#include <stdio.h>
#define N 1000
void Shift(int a[N], int n, int x)
{
int b[N];
for(int i=0; i<n-x; i++)
{
b[i]=a[x+i];
}
for(int i=n-x; i<n; i++)
{
b[i]=a[i+x-n];
}
for(int i=0; i<n; i++)
{
a[i]=b[i];
}
}
void Flip(int a[N], int n)
{
int temp;
int from=0, to=n/2-1;
while(from<to)
{
temp=a[from];
a[from]=a[to];
a[to]=temp;
from++;
to--;
}
}
int main()
{
int n, k, x;
int a[N];
while(scanf("%d %d", &n, &k)!=EOF)
{
for(int i=0; i<n; i++)
{
a[i]=i+1;
}
for(int i=0; i<k; i++)
{
scanf("%d", &x);
Shift(a, n, x);
Flip(a, n);
}
bool isfirst=true;
for(int i=0; i<n; i++)
{
if(isfirst) isfirst=false;
else printf(" ");
printf("%d", a[i]);
}
printf("\n");
}
return 0;
}
发表于 2018-02-25 08:34:32
回复(1)
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
void shift(vector<int>& arr, int n) { //数组循环移位（左移n位）
reverse(arr.begin(), arr.begin() + n);
reverse(arr.begin() + n, arr.end());
reverse(arr.begin(), arr.end());
}
int main() {
int n, k;
while (cin >> n >> k) {
vector<int>card(n);
for (int i = 0; i < n; i++) {
card[i] = i + 1;
}
while (k--) {
int x;
cin >> x;
shift(card, x);
reverse(card.begin(), card.begin() + card.size() / 2); //flip
}
for (const auto& e : card) {
cout << e << " ";
}
cout << endl;
}
return 0;
}
发表于 2024-03-04 12:03:29
回复(0)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
//#define count_len(x) (sizeof((x)) / sizeof(x)[0])
vector<int> a;
void shift(int x)//用reverse完成循环移位
{
//int n = sizeof(a) / sizeof(a[0]);
reverse(a.begin(),a.begin() + x);
reverse(a.begin() + x,a.end());
reverse(a.begin(),a.end());
}
void flip(int n)
{
if(n % 2 == 0)//奇数偶数判断
{
reverse(a.begin(),a.begin() + (n / 2));
}
else
{
reverse(a.begin(),a.begin() + (n - 1) / 2);
}
}
int main(void)
{
int n,k,x;
while(cin >> n >> k)
{
for(int i = 0;i < n;i++)
a.push_back(i + 1);
for(int i = 0;i < k;i++)
{
cin >> x;
shift(x);
flip(n);
}
for(int i = 0;i < a.size();i++)
cout << a[i] << ' ';
}
return 0;
}
编辑于 2021-01-27 15:35:53
回复(0)
#include<stdio.h> int main() { int n,m,k,i,j,t,a[1000]; scanf("%d%d",&n,&m); for(i=0;i<n>0;j--) {//交换 t=a[j];a[j]=a[j-1];a[j-1]=t; } } //2.前面一半倒序 int w1=n/2-1;//要交换的最后一个数值 for(i=0;i<(n/4);i++)//交换的次数 {//交换 t=a[i];a[i]=a[w1];a[w1]=t; w1--; } } for(i=0;i</n></stdio.h>
发表于 2020-12-23 22:49:58
回复(0)
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n,k,k1;
while(scanf("%d %d",&n,&k)!=EOF){
if(n==0&&k==0)
break;
vector<int> v(n);
for(int i=0;i<n;++i){
v[i]=i+1;
}
for(int i=0;i<k;++i){
scanf("%d",&k1);
reverse(v.begin(),v.begin()+k1);
reverse(v.begin()+k1,v.end());
reverse(v.begin(),v.end());
reverse(v.begin(),v.begin()+n/2);
}
printf("%d",v[0]);
for(int i=1;i<n;++i){
printf(" %d",v[i]);
}
printf("\n");
}
return 0;
}
编辑于 2020-04-27 14:21:39
回复(0)
def help(num , t):
arr1 = []
arr2 = []
if len(num)%2 == 0:
len1 = (len(num))//2
else:
len1 = (len(num)-1)//2
arr1 = num[t:] + num[0:t]
arr2 = arr1[:len1][::-1] + arr1[len1:]
return arr2
while True:
try:
n, k = map(int,input().strip().split())
if n == 0 and k == 0 :
break
b = [i for i in range(1, n+1)]
for _ in range(k):
x = int(input().strip())
b = help(b, x)
print(" ".join(map(str,b)))
except:
break
发表于 2020-04-12 18:39:15
回复(0)
好粗笨的方法..居然也过了。求java大神给更好的方案
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int n=sc.nextInt();
int k=sc.nextInt();
if(n==0)break;
List<Integer>list=new ArrayList<>();
for(int i=1;i<=n;i++)
list.add(i);
while(k-->0) {
int x=sc.nextInt();
list=reverse(list,x);
list=filp(list);
}
System.out.print(list.get(0));
for(int i=1;i<n;i++)
System.out.print(" "+list.get(i));
System.out.println();
}
}
private static List<Integer> filp(List<Integer> list) {
List<Integer>after=new ArrayList<>();
int len;
if(list.size()%2==0)
len=list.size()/2;
else
len=(list.size()-1)/2;
for(int i=0;i<len;i++)
after.add(list.get(i));
Collections.reverse(after);
for(int i=len;i<list.size();i++)
after.add(list.get(i));
return after;
}
private static List<Integer> reverse(List<Integer> list, int x) {
List<Integer>after=new ArrayList<>();
for(int i=x;i<list.size();i++)
after.add(list.get(i));
for(int i=0;i<x;i++)
after.add(list.get(i));
return after;
}
}
发表于 2020-04-10 15:39:52
回复(0)
#include <stdio.h>
#include <stdlib.h>
void swap(int *, int, int);
void circ(int*, int);
void reverse(int*, int);
int main()
{
int n, k;
int p[1001] = {0};
while(~scanf("%d%d", &n, &k))
{
if(n == 0 && k == 0)
break;
int i;
for(i = 1; i <= n; i++)
p[i] = i;
for(i = 1; i <= k; i++)
{
int t;
scanf("%d", &t);
swap(p, n, t);
reverse(p, n);
}
for(int i = 1; i <= n; i++)
if(i == 1)
printf("%d", p[i]);
else
printf(" %d", p[i]);
printf("\n");
}
return 0;
}
void swap(int d[], int n, int k)
{
for(int i = 0; i < k; i++)
circ(d, n);
}
void circ(int d[], int n)//模拟循环左移操作
{
int tmp = d[1];
for(int i = 1; i < n; i++)
d[i] = d[i + 1];
d[n] = tmp;
}
void reverse(int d[], int n)
{
int len = n / 2;
for(int i = 1; i <= len / 2; i++)
{
int tmp = d[i];
d[i] = d[len - i + 1];
d[len - i + 1] = tmp;
}
}
编辑于 2020-04-03 21:31:26
回复(0)
#include<stdio.h>
(737)#include<string.h>
int main(){
int n,k;
while(scanf("%d %d",&n,&k)!=EOF){
int i,j,x;
int c[n+1],d[n+1];
for(i=1;i<=n;i++){
c[i]=i;
}
for(i=0;i<k;i++){
int num=1;
scanf("%d",&x);
for(j=x+1;j<=n;j++){
d[num++]=c[j];
}
for(j=1;j<=x;j++){
d[num++]=c[j];
}
if(n%2!=0) num=(n-1)/2;
else num=n/2;
int h=1;
for(j=num;j>=1;j--){
c[h++]=d[j];
}
for(j=num+1;j<=n;j++){
c[h++]=d[j];
}
}
for(i=1;i<=n;i++){
printf("%d ",c[i]);
}
printf("\n");
}
return 0;
}
//纯C没办法，两个数组模拟吧
发表于 2020-03-28 22:19:24
回复(0)
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
int n,k;
while(cin>>n>>k){
if(n==0&&k==0) break;
string s[1000];
for(int i=1;i<=n;i++)
s[i-1]=to_string(i);
while(k--){
int pos;
cin>>pos;
int count=0;
string s1[1000];
for(int i=pos;i<n;i++) s1[count++]=s[i];
for(int i=pos-1;i>=0;i--) s[i+n-pos]=s[i];
for(int i=0;i<n-pos;i++) s[i]=s1[i];
reverse(s,s+n/2);
}
for(int i=0;i<n;i++) cout<<s[i]<<" ";
cout<<endl;
}
return 0;
}
编辑于 2020-03-17 20:34:42
回复(0)
#include<iostream>
#include<string>
#define N 1000
using namespace std;
void flip(int a[],int from,int to){
int i = from;
int j = to;
while(i<j){
int temp = a[i];
a[i] = a[j];
a[j]=temp;
i--;
j++;
}
}
void shift(int a[],int n,int x){
int b[N];
int i;
for(i=0;i<n-x;i++){
b[i]=a[i+x];
}
for(i=n-x; i<n; i++)
{
b[i]=a[i+x-n];
}
for(i=0;i<n;i++)
a[i]=b[i];
}
int main(){
int n,k,x;
int a[N];
while(scanf("%d %d",&n,&k)!=EOF && n!=0){
for(int i=0;i<n;i++)
a[i]=i+1;
while(k-- >0){
scanf("%d",&x);
shift(a,n,x);
flip(a,0,n/2-1);
}
for(int j=0;j<n;j++){
if(j==0)
cout<<a[j];
else
cout<<" "<<a[j];
}
cout<<endl;
}
return 0;
}
#include<string>
#define N 1000
using namespace std;
void flip(int a[],int from,int to){
int i = from;
int j = to;
while(i<j){
int temp = a[i];
a[i] = a[j];
a[j]=temp;
i--;
j++;
}
}
void shift(int a[],int n,int x){
int b[N];
int i;
for(i=0;i<n-x;i++){
b[i]=a[i+x];
}
for(i=n-x; i<n; i++)
{
b[i]=a[i+x-n];
}
for(i=0;i<n;i++)
a[i]=b[i];
}
int main(){
int n,k,x;
int a[N];
while(scanf("%d %d",&n,&k)!=EOF && n!=0){
for(int i=0;i<n;i++)
a[i]=i+1;
while(k-- >0){
scanf("%d",&x);
shift(a,n,x);
flip(a,0,n/2-1);
}
for(int j=0;j<n;j++){
if(j==0)
cout<<a[j];
else
cout<<" "<<a[j];
}
cout<<endl;
}
return 0;
}
发表于 2020-03-14 10:21:57
回复(0)
#include<iostream>
using namespace std;
void shift(int *a,int n,int m)
{if(m>0){
int end=a[n-1];
for(int i=n-1;i>=0;i--)
{
a[i]=a[i-1];
}
m--;
a[0]=end;
shift(a,n,m);
}
}
void flip(int *a,int n)
{
int k=0;
if(n%2==0)k=n/2;
else k=(n-1)/2;
int j=k/2;
for(int i=0;i<j;i++)
{
int t=a[i];
a[i]=a[k-i-1];
a[k-i-1]=t;
}
}
int main()
{
int *a;
int n,m,k;
while(cin>>n>>k)
{
if(n==0&&k==0)break;
a=new int[n];
for(int i=0;i<n;i++)
{
a[i]=i+1;
}
for(int i=0;i<k;i++)
{
cin>>m;
shift(a,n,n-m);
flip(a,n);
}
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
}
}
using namespace std;
void shift(int *a,int n,int m)
{if(m>0){
int end=a[n-1];
for(int i=n-1;i>=0;i--)
{
a[i]=a[i-1];
}
m--;
a[0]=end;
shift(a,n,m);
}
}
void flip(int *a,int n)
{
int k=0;
if(n%2==0)k=n/2;
else k=(n-1)/2;
int j=k/2;
for(int i=0;i<j;i++)
{
int t=a[i];
a[i]=a[k-i-1];
a[k-i-1]=t;
}
}
int main()
{
int *a;
int n,m,k;
while(cin>>n>>k)
{
if(n==0&&k==0)break;
a=new int[n];
for(int i=0;i<n;i++)
{
a[i]=i+1;
}
for(int i=0;i<k;i++)
{
cin>>m;
shift(a,n,n-m);
flip(a,n);
}
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
}
}
发表于 2020-03-10 10:33:12
回复(0)
#include <iostream>
#include <algorithm>
using namespace std;
void shift(int *number, int length, int i)
{
int numbersb[i],numbersa[length-i];
for(int j = 0;j<i;j++)
{
numbersb[j] = number[j];
}
for(int k = 0;k<length-i;k++)
{
numbersa[k] = number[i+k];
}
for(int p = 0;p<length;p++)
{
if(p<length-i)
{
number[p] = numbersa[p];
}
else
{
number[p] = numbersb[p-length+i];
}
}
}
int main()
{
int n,k;
cin>>n>>k;
int numbers[n];
for(int i = 0;i<n;i++)
{
numbers[i] = i+1;
}
for(int h = 0;h<k;h++)
{
int index = 0;
cin>>index;
shift(numbers, n, index);
int half = n%2==0?n/2:(n-1)/2;
reverse(numbers, numbers+half);
}
for(int i = 0;i<n;i++)
{
cout<<numbers[i]<<" ";
}
return 0;
}
发表于 2019-09-20 22:18:24
回复(0)
问题信息
难度：
34条回答
38收藏
3848浏览
通过挑战的用户
查看代码-
2023-02-28 00:25:36 -
2022-09-04 17:56:11
-
2022-08-29 20:33:43
-
2022-07-21 11:21:56 -
2022-07-18 10:43:36
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
