盘子从厨师右边流向左边
厨师连续做n盘寿司,放入回转寿司的传送列中
最初的分叉点:
最初的b盘寿司会流向上面的传送列,后面的n-b盘寿司流向下面的传送列
或者
最初的b盘寿司会流向下面的传送列,后面的n-b盘寿司流向下面的传送列
1<=b<=n-1
上面的列和下面的列都坐着客人
上面的客人:会吃掉送过来的所有寿司,全部吃掉以后,会以最初传送过来的顺序或者与之相反的顺序把盘子放回传送列
下面的客人和上面的客人完全一样。
店员会把传送过来的空盘子叠成一叠,有可能叠成上面客人的盘子在上,也有可能叠成下面的客人的盘子在上
碟子一共有10种(0,1,2,3,4,5,6,7,8,9)
问最后一共有多少被叠起来的可能
比如,流过来的碟子是0,1,2的时候
一共有012,021,102,120,201,210这6种顺序
输入格式:
数据的个数L
数据1
数据2
…
数据L
各数据代表盘子的排列方式(2<=盘子数量<=100)
输出
输出可能的排列数量
<例1>
输入
3
001
12345
0000
输出
3
18
1
<例2>
输入
2
012
1234
输出
6
12
(还有一组是50个的比较大的数据,这个时候我自己写的程序运行就会直接结束)
以下是代码雏形
只需要修改reverse swap和chk_isnew(这个函数我应该没写错)部分
(自己写了要求的函数部分,但是结果不对)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int item;
typedef struct node *link;
#define MAX_LEN 100
#define MAX_RESULTS 1000
struct node
{
char *p;
link next;
};
link NEW(char *inp, link next)
{
link x = malloc(sizeof(*x));
x->p = inp;
x->next = next;
return x;
}
void reverse(int sp,int ep,char*in)
{
int i;
char temp;
for(i=0;i<(ep-sp+1)/2;i++){
temp=in[sp+i];
in[sp+i]=in[ep-(i+1)];
in[ep-(i+1)]=temp;
}
//reverse in[sp]...in[ep-1]
}
void swap(int sp,int ep,char *in)
{
int i,j,k;
char temp[101];
char box1[101];
char box2[101];
for(i=0;i<sp;i++){
temp[i]=in[i];
}
for(j=0;j<ep-sp;j++){
box1[j]=in[sp+j];
}
for(k=0;k<sp;k++){
box2[k]=temp[k];
}
*in=strcat(box1,box2);
//swap in[0]~in[sp-1] by in[sp]~in[ep-1]
}
int chk_isnew(char *in, link *p_head)
{
link t=*p_head;
while(t!=NULL)
{
if(strcmp(t->p,in)==0) return 0;
else t=t->next;
}
char *store = (char *)malloc(sizeof(char)*MAX_LEN);
memcpy(store,in,sizeof(char)*MAX_LEN);
*p_head = NEW(store, *p_head);
return(1);
}
int main(void)
{
link head;
int num, cnt, i;
scanf("%d", &num);
int *result = (int *)malloc(sizeof(int)*MAX_RESULTS);
char *dish;
char *tmp_dish;
for(cnt=0; cnt<num; cnt++)
{
result[cnt] = 0;
head = NULL;
dish = (char *)malloc(sizeof(char)*MAX_LEN);
memset(dish,0x00,sizeof(char)*MAX_LEN);
tmp_dish = (char *)malloc(sizeof(char)*MAX_LEN);
scanf("%s", dish);
memcpy(tmp_dish,dish,sizeof(char)*MAX_LEN);
int len = strlen(dish);
for(i=1; i<len; i++)
{
int rev, swp;
for(rev=0; rev<4; rev++)
{
switch(rev)
{
case 0:
break;
case 1:
reverse(0,i,tmp_dish); // reverse 1st half
break;
case 2:
reverse(i,len,tmp_dish); // reverse 2nd half
break;
case 3:
reverse(0,i,tmp_dish); // reverse 1st half
reverse(i,len,tmp_dish); // reverse 2nd half
break;
}
for(swp=0; swp<2; swp++)
{
switch(swp)
{
case 0:
break; //not swap
case 1:
swap(i,len,tmp_dish); //swap
break;
}
if(chk_isnew(tmp_dish, &head)) result[cnt]++;
}
memcpy(tmp_dish,dish,sizeof(char)*MAX_LEN);
}
}
link t = head;
while(t->next!=NULL)
{
t = t->next;
}
link r;
t = head;
while(t->next!=NULL)
{
r = t;
t = t->next;
free(r->p);
free(r);
}
free(dish);
free(tmp_dish);
}
for(cnt=0; cnt<num; cnt++)
{
printf("%d\n",result[cnt]);
}
return 0;
}
要求改写reverse,swap和chk_isnew的函数部分(chk_isnew应该没有错)
非常长的问题有劳了