数据结构 第一次实验总结变着法子玩约瑟夫环和一元多项式
程序员文章站
2022-06-07 14:39:11
...
约瑟夫环的不同玩法
约瑟夫环作为数据结构的经典问题，本来就会演化为各种各样的问题，我前面也写了用三种方法实现约瑟夫环问题，请点击传送门
这边的话，是我们老师给了我们一个上机实验的任务，然后这里是对约瑟夫环问题进行了一点小小的改变，不变实质，变问题。
第一个问题
编号为1，2，…，n的n个人按顺时针方向围坐在一张圆桌周围，每人持有一个密码（正整数）。一开始任选一个正整数m作为报数上限值，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数，报m的那个人出列，将他的密码作为新的m值，从他顺时针方向的下一个人开始重新从1报数，数到m的那个人又出列；如此下去，直至圆桌周围的人全部出列为止。要求按出列顺序输出n个人的编号。
我们实现约瑟夫环的思维是，对一个循环的结构不断遍历，并且遍历到一定的次数，我们就弹出该元素，那么第一个问题，并不难解决，我们只要每一次遍历都改变这个一定次数就可以了。
代码：
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int num[2];
struct node *next;
}list;
list * creat(int n);
void print(list * head);
void find_died(list *head,int k);
int main(){
int n,k;
scanf("%d %d",&n,&k);
list *head=creat(n);
//print(head);
find_died(head,k);
return 0;
}
list * creat(int n){
list *head=(list*)malloc(sizeof(list));
list *q,*p=head;
scanf("%d",&p->num[0]);
p->num[1]=1;
for(int i=2;i<=n;i++){
q=(list*)malloc(sizeof(list));
scanf("%d",&q->num[0]);
q->num[1]=i;
p->next=q;
p=p->next;
}
p->next=head;
return head;
}
void print(list * head){
list * p=head;
while(p->next!=head){
printf("%d->%d\n",p->num[1],p->num[0]);
p=p->next;
}
printf("%d->%d\n",p->num[1],p->num[0]);
}
void find_died(list *head,int k){
list * p = head;
list * q;
while(p->next!=p){
for(int i=0;i<k-1;i++){
q=p;
p=p->next;
}
q->next=p->next;
printf("%d ",p->num[1]);
k=p->num[0];
free(p);
p=q->next;
}
printf("%d ",p->num[1]);
}
- 代码利用的数据结构为循环链表，该结构很容易解出该问题，当然仁者见仁智者见智，利用队列或者遍历数组当然也可以实现。
- 我个人觉得循环链表相对于遍历数组有优势，一个是利用指针的不断开辟空间，能做到对空间的完全利用，如果开辟数组的话，会导致，在不断的弹出之后，数组的空间浪费。
- 如果利用队列的话，等于是利用了队列的后进前出，整个构成了一个循环的过程，对于队列结构比较熟练的话，思路会很明确，当然，你也得提前开辟很大的空间，所以虽然方法很多，但是我觉得还是循环链表相对于其他的要好很多。
好了，看第二个问题
简化，输入两个数字，一个为总人数，一个为数到几弹出，输出一个弹出的序列，几乎对约瑟夫环没有什么更改，直接上代码。
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int x;
struct node *next;
}list;
//鏋勫缓寰幆閾捐〃
list* creat(int n){
list *head=(list*)malloc(sizeof(list));
head->x=1;
list *q,*p=head;
for(int i=2;i<=n;++i){
q=(list*)malloc(sizeof(list));
q->x=i;
p->next=q;
p=p->next;
}
p->next=head;
return head;
}
//鍒╃敤璇ュ嚱鏁版壘鍒版瘡涓€娆′細涓㈠け鐨勪汉
void find_died(list *head,int d){
list *p=head,*q;
while(p->next!=p){
for(int i=1;i<d;i++){
q=p;
p=p->next;
}
q->next=p->next;
printf("%d ",p->x);
free(p);
p=q->next;
}
printf("%d ",p->x);
}
int main(){
int n,d;
scanf("%d %d",&n,&d);
list *head=creat(n);
find_died(head,d);
return 0;
}
没什么问题，看第三个。
#include <stdio.h>
#include <stdlib.h>
typedef struct Person {
int order;
struct Person * next;
} Person;
Person * pHead = NULL; // 全局变量
Person * pFront = NULL;
Person * per = NULL;
int n, m;
int b[100], k;
// 函数
void Create();
void Joseph(int number, int m);
int main()
{
scanf("%d %d", &n, &m);
int i;
int a[n];
for (i = n - m ; i < n; i++)
scanf("%d", &a[i]);
for (i = 1; i <= n; i++) {
pHead = NULL;
pFront = NULL;
k = 0;
int flag = 1;
Create();
per = pHead;
Joseph(n, i);
for (int j = n - m; j < n; j++) {
if (a[j] != b[j]) {
flag = 0;
break;
}
}
if (flag == 1) {
printf("%d", i);
return 0;
}
}
printf("0");
return 0;
}
void Create() {
Person * tail;
for (int i = 0; i < n; i++) {
Person * person;
person = (Person *) malloc(sizeof(Person));
person->order = i + 1;//对本身的数据结构赋值
if (pHead == NULL)//构造链表的不同方法
pHead = person;
else
tail->next = person;
tail = person;
}
tail->next = pHead;
pFront = tail;
}
void Joseph(int number, int m) {
if (number == 0) {
return;
}
int count = 1;
Person * p = NULL;
while (count != m) {
per = per->next;
pFront = pFront->next;
count++;
}
p = per;
pFront->next = per->next;
b[k++] = p->order;
per = per->next;
free(p);
Joseph(number - 1, m);
}
- 这里我们需要用到递归，因为会节省很大的代码量，如果不使用递归的话，我们需要写好几个循环来构造数组，判断等等操作。
- 我们用一个大的for循环，每一次循环都会通过递归获得一个b数组，之后我们通过循环判断该数组是否符合，不符合的话直接break，跳出循环，到下一个循环。不断的判断。
- 思路的话比较容易想到，但是代码实现的话还是有些难度的。
一元多项式的各种操作
一元多项式这个实验，一般情况下是在顺序表章节会给的任务，也确实，虽然对于线性结构的顺序表来说，可能不太友好，因为存在空间分配等等问题，但是，如果利用链式结构实现的话应该会方便许多。
题目一
这里我发现，c语言怎么搞都会有问题。????但是我本人又不太明白问题在哪????
希望有人能发现问题吧。
代码：
#include<stdio.h>
#include<stdlib.h>
int main()
{
int n;
int a[1000][2];
scanf("%d", &n);
getchar();
for(int i=1; i<=n; i++) //输入
scanf("(%d,%d)", &a[i][1], &a[i][2]);
fflush(stdin);
getchar();
for(int i=1; i<n; i++) //冒泡排序
for(int j=1; j<n-i; j++)
if(a[j][2]>a[j+1][2])
{
int t=a[j+1][2];
a[j+1][2]=a[j][2];
a[j][2]=t;
t=a[j+1][1];
a[j+1][1]=a[j][1];
a[j][1]=t;
}
for(int i=1; i<=n; i++) //输出
{
printf("%d", a[i][1]);
if(a[i][2]==0)
printf("");
else if(a[i][2]==1)
printf("X");
else
printf("X^%d", a[i][2]);
if(i!=n && a[i+1][1]>0)
printf("+");
}
}
题目二
这里我直接放弃了链表，这个pta多多少少沾点问题，真的在搞人心态。
代码：
#include<stdio.h>
#include<stdlib.h>
int sub(int max[][3], int min[][3], int n1, int n2)
{
int cnt=n1+1;
for(int i=1; i<=n2; i++)
{
int flag=1; //标记是否可以加到现有的项中
for(int j=1; j<=n1; j++)
{
if(min[i][2]==max[j][2])
{
max[j][1]+=min[i][1]; //加到了现有的项
flag=0;
break;
}
}
if(flag) //如果没有加到则放在表达式的后面
{
max[cnt][1]=min[i][1];
max[cnt++][2]=min[i][2];
}
}
return cnt-1;
}
void sort(int a[][3], int n) //按指数对所有项进行从小到大排序
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n-i; j++)
{
if(a[j][2]>a[j+1][2])
{
int t=a[j+1][2];
a[j+1][2]=a[j][2];
a[j][2]=t;
t=a[j+1][1];
a[j+1][1]=a[j][1];
a[j][1]=t;
}
}
}
}
void print(int a[][3], int n) //输出
{
int cnt=0;
for(int i=1; i<=n; i++)
{
if(a[i][1]==0)
{
if(cnt!=0 && a[i+1][1]>0 && i!=n)
printf("+");
}
else if(a[i][1]==1)
{
if(a[i][2]==0){
printf("1");
cnt=1;
}
else if(a[i][2]==1){
printf("X");
cnt=1;
}
else{
printf("X^%d", a[i][2]);
cnt=1;
}
if(a[i+1][1]>0 && i!=n)
printf("+");
}
else if(a[i][1]==-1)
{
if(a[i][2]==0){
printf("-1");
cnt=1;
}
else if(a[i][2]==1){
printf("-X");
cnt=1;
}
else{
printf("-X^%d", a[i][2]);
cnt=1;
}
if(a[i+1][1]>0 && i!=n)
printf("+");
}
else
{
if(a[i][2]==0){
printf("%d", a[i][1]);
cnt=1;
}
else if(a[i][2]==1){
printf("%dX", a[i][1]);
cnt=1;
}
else{
printf("%dX^%d", a[i][1], a[i][2]);
cnt=1;
}
if(a[i+1][1]>0 && i!=n)
printf("+");
}
}
}
int main()
{
int n1, n2;
int n;
int a[100][3], b[100][3];
scanf("%d", &n1); //输入第一个
getchar();
for(int i=1; i<=n1; i++)
scanf("(%d,%d)", &a[i][1], &a[i][2]);
scanf("%d", &n2); //输入第二个
getchar();//利用getchar清楚缓存区
for(int i=1; i<=n2; i++)
scanf("(%d,%d)", &b[i][1], &b[i][2]);
n=n1>n2?sub(a, b, n1, n2):sub(b, a, n2, n1);
if(n1>n2)
{
sort(a,n);
print(a,n);
}
else
{
sort(b,n);
print(b,n);
}
}
题目三
这里注意所谓的减法，我们只需要对加法的代码进行变换就可以了，只需要将输入的数据变成其相反数便可。因此不难，这里我提供一段java代码
代码：
import java.util.Scanner;
class Calculator{
//计算器减法操作
public int[] subtraction(int[]nums1,int[]nums2){ //nums1减num2
int[]sum = new int[nums1.length+nums2.length];
int x=0,y=0,z=0;
while(x<nums1.length||y<nums2.length){
if (x>=nums1.length&&y<nums2.length){ //当num1长度小于num2时
sum[z] = (-1)*nums2[y]; //系数变为负数
sum[z+1] = nums2[y+1];
z=z+2;
y=y+2;
}
if (y>=nums2.length&&x<nums1.length){ //当num2长度小于num1时
sum[z] = nums1[x]; //系数不变
sum[z+1] = nums1[x+1];
z=z+2;
x=x+2;
}
if(x<nums1.length&&y<nums2.length&&nums1[x+1]<nums2[y+1]){ //第一组指数小于第二组，第一组到下一个节点
sum[z] = nums1[x];
sum[z+1] = nums1[x+1];
z = z+2;
x = x+2;
}
else if (x<nums1.length&&y<nums2.length&&nums1[x+1]==nums2[y+1]){ //指数相等，系数相加
sum[z] = nums1[x]-nums2[y];
sum[z+1] = nums1[x+1];
z = z+2;
x = x+2;
y = y+2;
}
else if(x<nums1.length&&y<nums2.length&&nums1[x+1]>nums2[y+1]){ //第二组指数小于第一组，第二组到下一节点
sum[z] = (-1)*nums2[y];
sum[z+1] = nums2[y+1];
z = z+2;
y = y+2;
}
}
return sum;
}
//打印出结果
public void print(int[]sum){
int index=0,judge=0;
while(index < sum.length){
if (sum[index+1]!=0&&sum[index]!=0){ //指数和系数都不为0的情况
if (sum[index+1]==1){
judge++;
System.out.print(sum[index]+"X");
}
else{
judge++;
System.out.print(sum[index]+"X^"+sum[index+1]);
}
if (index+2<sum.length){
if (sum[index+2]>0){
System.out.print("+");
}
}
}
else if(sum[index+1]==0&&sum[index]!=0){ //指数为0，系数不为0的情况
judge++;
System.out.print(sum[index]);
if (index+2<sum.length){
if (sum[index+2]>0){
System.out.print("+");
}
}
}
else if(sum[index]==0){ //系数为0的情况
if (index+2<sum.length){
if (sum[index+2]>0){
System.out.print("+");
}
}
}
index = index+2;
}
if (judge==0){
System.out.println(0);
}
}
}
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n=input.nextInt();
input.nextLine();
String string1 = input.nextLine();
int m=input.nextInt();
input.nextLine();
String string2 = input.nextLine();
string1 = string1.replace("(","");
string1 = string1.replace(")",",");
string2 = string2.replace("(","");
string2 = string2.replace(")",",");
String[]strings1 = string1.split(",");
String[]strings2 = string2.split(",");
int[]nums1 = new int[n*2];
int[]nums2 = new int[m*2];
Calculator calculator = new Calculator();
for(int i=0;i<strings1.length-1;i++){
if (i%2==0){
nums1[i] = Integer.parseInt(strings1[i]);
nums1[i+1] = Integer.parseInt(strings1[i+1]);
}
}
for(int i=0;i<strings2.length-1;i++){
if (i%2==0){
nums2[i] = Integer.parseInt(strings2[i]);
nums2[i+1] = Integer.parseInt(strings2[i+1]);
}
}
int[]sum = calculator.subtraction(nums1,nums2);
calculator.print(sum);
}
}
题目四
乘法：
代码：
#include<stdio.h>
#include<stdlib.h>
int map(int a[][3], int b[][3], int c[][3], int n1, int n2);
void sort(int a[][3], int n);
void print(int a[][3], int n);
int main()
{
int n1, n2;
int n;
int a[100][3], b[100][3], c[100][3];
scanf("%d ", &n1);
for(int i=1; i<=n1; i++)
scanf("(%d,%d)", &a[i][1], &a[i][2]);
scanf("%d ", &n2);
for(int i=1; i<=n2; i++)
scanf("(%d,%d)", &b[i][1], &b[i][2]);
n=map(a, b, c, n1, n2);
sort(c, n);
print(c, n);
return 0;
}
int map(int a[][3], int b[][3], int c[][3], int n1, int n2)
{
int cnt=1;
for(int i=1; i<=n1; i++)
{
for(int j=1; j<=n2; j++)
{
int flag=1;
int c1=a[i][1]*b[j][1];
int c2=a[i][2]+b[j][2];
for(int k=1; k<cnt; k++)
if(c[k][2]==c2)
{
c[k][1]+=c1;
flag=0;
break;
}
if(flag)
{
c[cnt][1]=c1;
c[cnt++][2]=c2;
}
}
}
return cnt-1;
}
void sort(int a[][3], int n)
{
for(int i=1; i<=n; i++)
for(int j=1; j<=n-i; j++)
if(a[j][2]>a[j+1][2])
{
int t=a[j+1][2];
a[j+1][2]=a[j][2];
a[j][2]=t;
t=a[j+1][1];
a[j+1][1]=a[j][1];
a[j][1]=t;
}
}
void print(int a[][3], int n)
{
int cnt=0;
for(int i=1; i<=n; i++)
{
if(a[i][1]==0)
{
if(cnt!=0 && a[i+1][1]>0 && i!=n)
printf("+");
}
else if(a[i][1]==1)
{
if(a[i][2]==0){
printf("1");
cnt=1;
}
else if(a[i][2]==1){
printf("X");
cnt=1;
}
else{
printf("X^%d", a[i][2]);
cnt=1;
}
if(a[i+1][1]>0 && i!=n)
printf("+");
}
else if(a[i][1]==-1)
{
if(a[i][2]==0){
printf("-1");
cnt=1;
}
else if(a[i][2]==1){
printf("-X");
cnt=1;
}
else{
printf("-X^%d", a[i][2]);
cnt=1;
}
if(a[i+1][1]>0 && i!=n)
printf("+");
}
else
{
if(a[i][2]==0){
printf("%d", a[i][1]);
cnt=1;
}
else if(a[i][2]==1){
printf("%dX", a[i][1]);
cnt=1;
}
else{
printf("%dX^%d", a[i][1], a[i][2]);
cnt=1;
}
if(a[i+1][1]>0 && i!=n)
printf("+");
}
}
}
题目五
求值：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct node{
double num[2];
struct node * next;
}list;
list * creat(int n){
if(n==0)
return NULL;
list * head=(list*)malloc(sizeof(list));
list * q,* p=head;
scanf("(%lf,%lf)",&head->num[0],&head->num[1]);
for(int i=1;i<n;i++){
q=(list*)malloc(sizeof(list));
scanf("(%lf,%lf)",&q->num[0],&q->num[1]);
p->next=q;
p=p->next;
}
p->next=NULL;
return head;
}
double add(list *a,double x)//求和
{
list *q=a;
double answer=0;
while(q!=NULL){
answer+=(q->num[0]*pow(x,q->num[1]));
q=q->next;
}
return answer;
}
int main(){
int n;
scanf("%d ",&n);
fflush(stdin);
list * head=creat(n);
double x;
scanf("%lf ",&x);
getchar();
printf("%.0lf",add(head,x));
return 0;
}
题目六：
求导：
#include<stdio.h>
#include<stdlib.h>
void derivative(int list[][3],int n)
{
for(int i=1;i<=n;i++){
if(list[i][1]==0||list[i][2]==0){
list[i][1]=0;
list[i][2]=0;
}
else{
list[i][1]*=list[i][2];
list[i][2]-=1;
}
}
}
void sort(int a[][3], int n) //按指数对所有项进行从小到大排序
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n-i; j++)
{
if(a[j][2]>a[j+1][2])
{
int t=a[j+1][2];
a[j+1][2]=a[j][2];
a[j][2]=t;
t=a[j+1][1];
a[j+1][1]=a[j][1];
a[j][1]=t;
}
}
}
}
void print(int a[][3], int n)
{
int cnt=0;
for(int i=1; i<=n; i++)
{
if(a[i][1]==0)
{
if(cnt!=0 && a[i+1][1]>0 && i!=n)
printf("+");
}
else if(a[i][1]==1)
{
if(a[i][2]==0){
printf("1");
cnt=1;
}
else if(a[i][2]==1){
printf("X");
cnt=1;
}
else{
printf("X^%d", a[i][2]);
cnt=1;
}
if(a[i+1][1]>0 && i!=n)
printf("+");
}
else if(a[i][1]==-1)
{
if(a[i][2]==0){
printf("-1");
cnt=1;
}
else if(a[i][2]==1){
printf("-X");
cnt=1;
}
else{
printf("-X^%d", a[i][2]);
cnt=1;
}
if(a[i+1][1]>0 && i!=n)
printf("+");
}
else
{
if(a[i][2]==0){
printf("%d", a[i][1]);
cnt=1;
}
else if(a[i][2]==1){
printf("%dX", a[i][1]);
cnt=1;
}
else{
printf("%dX^%d", a[i][1], a[i][2]);
cnt=1;
}
if(a[i+1][1]>0 && i!=n)
printf("+");
}
}
}
int main()
{
int n;
int list[100][3];
scanf("%d ", &n);
for(int i=1; i<=n; i++)
scanf("(%d,%d)", &list[i][1], &list[i][2]);
sort(list,n);
derivative(list,n);
print(list,n);
}
上一篇： 7-4 水仙花数