问题描述
-
约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后 [1] 结果+1即为原问题的解。
-
数学上的一元多项式的表示是p(x) = p0 + p1 * x + p2 * x^2 + p3 * x^3 + … + pn * x^n;
用链表来表示就是p = (p0, p1, p2, … , pn);
所谓的多项式相加就是同类项的合并，也就是两条链表的合并。
采用单链表保存多项式，链表的每个结点表示多项式的每一非零项，链表应该按有序排列。
直接上源码
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int id ;
int psd ;
struct node * next ;
}listnode,*linklist;
void init_list(linklist * h);
void input_data(int num ,linklist h);
void out_queue(int s_key , linklist h);
int main(){
int num , s_key ;
linklist h ;
init_list(&h);
scanf("%d",&num);
scanf("%d",&s_key);
input_data(num , h);
out_queue(s_key,h);
return 0 ;
}
void out_queue(int s_key ,linklist h){
linklist q = h ;
linklist p = q->next ;
s_key -- ;
while(p != p -> next){
if(p == h){
q = p ;
p = p->next ;
}
if(s_key == 0){
s_key = p->psd ;
printf("%d ",p->id);
q->next = p->next ;
free(p);
p = q->next ;
s_key -- ;
}
else{
q = p ;
p = p->next ;
s_key -- ;
}
}
free(h);
}
void input_data(int num ,linklist h){
linklist q , p;
p = h ;
int i = 1 ;
while(num){
q = (linklist)malloc(sizeof(listnode));
scanf("%d",&(q->psd));
q->id = i ;
num -- ;
i++ ;
q ->next = p->next ;
p->next = q ;
p = q ;
}
}
void init_list(linklist * h){
linklist q ;
* h = NULL ;
*h = (linklist)malloc(sizeof(listnode));
q = *h ;
q ->next = * h ;
}
求和差
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int zhishu ;
int xishu ;
struct node * next ;
}nodelist ,* linklist;
void init_list(linklist * h);
void input_data(linklist h ,int i);
void calcu(linklist h1 ,linklist h2);
void prt(linklist h);
void destroy(linklist h);
int main(){
linklist h1,h2 ;
init_list(&h1);
init_list(&h2);
input_data(h1,1);
input_data(h2,1);
calcu(h1 ,h2);
}
//通过传i的值来判断是"+"或"-"
void calcu(linklist h1 ,linklist h2){
linklist h3=NULL , s ,t;
init_list(&h3);
t = h3 ;
linklist p ,q ;
p = h1 ->next ;
q = h2 ->next ;
while(p!=NULL && q!=NULL){
s= (nodelist*)malloc(sizeof(nodelist));
if(p->zhishu< q->zhishu){
s ->xishu = p->xishu ;
s->zhishu = p->zhishu ;
s-> next= t->next ;
t->next = s ;
t = s ;
p = p->next ;
}
else if(p->zhishu > q->zhishu){
s->zhishu = q->zhishu ;
s->xishu = q->xishu ;
s->next = t->next ;
t->next = s ;
t = s ;
q = q->next ;
}
else{
s->xishu = p->xishu + q->xishu ;
s->zhishu = p->zhishu;
if(s->xishu == 0){
free(s);
p = p->next ;
q = q->next ;
continue ;
}
s->next = t->next;
t->next = s ;
t = s ;
q = q->next ;
p = p->next ;
}
}
while(p != NULL){
s = (linklist)malloc(sizeof(nodelist));
s->xishu = p->xishu ;
s->zhishu = p->zhishu ;
s->next = t->next ;
t ->next = s ;
t = s ;
p = p->next;
}
while(q != NULL){
s = (linklist)malloc(sizeof(nodelist));
s -> xishu= q->xishu ;
s->zhishu = q->zhishu ;
s->next = t->next ;
t->next = s ;
t = s ;
q = q->next ;
}
prt(h3);
destroy(h3);
destroy(h2);
destroy(h1);
}
void destroy(linklist h){
linklist p = h ;
h = h->next ;
while(h != NULL){
free(p);
p = h ;
h = h->next ;
}
free(h);
return ;
}
void prt(linklist h){
if(h->next == NULL){
printf("0");
return ;
}
linklist p ;
p = h->next ;
while(p!= NULL){
if(p->xishu < 0){
printf("-");
p->xishu = -p->xishu ;
}
printf("%d",p->xishu);
if(p->zhishu != 0){
printf("X");
if(p->zhishu != 1)
printf("^%d",p->zhishu);
}
p = p->next ;
if(p == NULL)break ;
if(p->xishu > 0){
printf("+");
}
}
}
void input_data(linklist h ,int i){
linklist p ,q ;
p = h ;
int num ;
scanf("%d",&num);
getchar();
if(num){
q = (linklist)malloc(sizeof(nodelist));
while((scanf("(%d,%d)",&(q->xishu) ,&(q->zhishu)))!=EOF&& num){
q->xishu*= i ;
q->next = p->next;
p->next = q ;
p = q ;
num -- ;
if(num == 0)break ;
q = (linklist)malloc(sizeof(nodelist));
}
}
else{
return ;
}
}
void init_list(linklist * h){
*h = NULL ;
*h = (linklist)malloc(sizeof(nodelist));
(*h)->next =NULL ;
}
求积
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node{
int zhishu ;
int xishu ;
struct node * next ;
}nodelist ,* linklist;
void init_list(linklist * h);
void input_data(linklist h ,int i);
void calcu(linklist h1 ,linklist h2);
void prt(linklist h);
void destroy(linklist h);
int main(){
linklist h1,h2 ;
init_list(&h1);
init_list(&h2);
input_data(h1,1);
input_data(h2,1);
calcu(h1 ,h2);
return 0;
}
void calcu(linklist h1 ,linklist h2){
linklist h3,s,t ;
init_list(&h3);
memset(h3 ,0 ,sizeof(h3));
linklist p , q ;
p = h1->next ;
t = h3 ;
while(p){
q = h2->next ;
while(q){
s = (linklist)malloc(sizeof(nodelist));
s->xishu = p->xishu*q->xishu ;
s->zhishu = p->zhishu+q->zhishu ;
if(s->xishu == 0){
free(s) ;
q = q->next ;
continue ;
}
if(s->zhishu == t->zhishu){
t->xishu = t->xishu + s->xishu ;
free(s);
q= q->next ;
continue ;
}
else{
if(t->zhishu < s->zhishu){
s->next = t->next ;
t->next = s ;
t = s ;
}
else{
t->zhishu = s->zhishu+t->zhishu ;
s->zhishu = t->zhishu -s->zhishu ;
t->zhishu = t->zhishu -s->zhishu ;
t->xishu = s->xishu+t->xishu ;
s->xishu = t->xishu - s->xishu ;
t->xishu = t->xishu - s->xishu ;
s->next = t->next ;
t->next = s ;
t = s ;
}
q= q->next ;
}
}
p = p->next ;
}
prt(h3);
destroy(h1);
destroy(h2);
destroy(h3);
}
void destroy(linklist h){
linklist p = h ;
h = h->next ;
while(h != NULL){
free(p);
p = h ;
h = h->next ;
}
free(h);
return ;
}
void prt(linklist h){
if(h->next == NULL){
printf("0");
return ;
}
linklist p ;
p = h->next ;
while(p!= NULL){
if(p->xishu < 0){
printf("-");
p->xishu = -p->xishu ;
}
printf("%d",p->xishu);
if(p->zhishu != 0){
printf("X");
if(p->zhishu != 1)
printf("^%d",p->zhishu);
}
p = p->next ;
if(p == NULL)break ;
if(p->xishu > 0){
printf("+");
}
}
}
void input_data(linklist h ,int i){
linklist p ,q ;
p = h ;
int num ;
scanf("%d",&num);
getchar();
if(num){
q = (linklist)malloc(sizeof(nodelist));
while((scanf("(%d,%d)",&(q->xishu) ,&(q->zhishu)))!=EOF&& num){
q->xishu*= i ;
q->next = p->next;
p->next = q ;
p = q ;
num -- ;
if(num == 0)break ;
q = (linklist)malloc(sizeof(nodelist));
}
}
else{
return ;
}
}
void init_list(linklist * h){
*h = NULL ;
*h = (linklist)malloc(sizeof(nodelist));
(*h)->next =NULL ;
}
取值
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct node{
int zhishu ;
int xishu ;
struct node * next ;
}nodelist ,* linklist;
void init_list(linklist * h);
void input_data(linklist h);
void calcu(linklist h);
void destroy(linklist h);
int main(){
linklist h ;
init_list(&h);
input_data(h);
calcu(h);
}
void calcu(linklist h){
double sum = 0;
int n ;
scanf("%d",&n);
linklist p ;
p = h->next ;
while(p){
sum += (p->xishu)*pow(n,(p->zhishu));
p = p->next ;
}
printf("%.0lf",sum);
destroy(h);
}
void destroy(linklist h){
linklist p = h ;
h = h->next ;
while(h != NULL){
free(p);
p = h ;
h = h->next ;
}
free(h);
return ;
}
void input_data(linklist h){
linklist p ,q ;
p = h ;
int num ;
scanf("%d",&num);
getchar();
if(num){
q = (linklist)malloc(sizeof(nodelist));
while((scanf("(%d,%d)",&(q->xishu) ,&(q->zhishu)))!=EOF&& num){
q->next = p->next;
p->next = q ;
p = q ;
num -- ;
if(num == 0)break ;
q = (linklist)malloc(sizeof(nodelist));
}
}
else{
return ;
}
}
void init_list(linklist * h){
*h = NULL ;
*h = (linklist)malloc(sizeof(nodelist));
(*h)->next =NULL ;
}
导数
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct node{
int zhishu ;
int xishu ;
struct node * next ;
}nodelist ,* linklist;
void init_list(linklist * h);
void input_data(linklist h);
void calcu(linklist h);
void prt(linklist h);
void destroy(linklist h);
int main(){
linklist h ;
init_list(&h);
input_data(h);
calcu(h);
}
void calcu(linklist h){
linklist p ,tmp ;
tmp = h ;
p = tmp->next ;
while(p){
p->xishu = p->xishu * p->zhishu ;
p->zhishu = p->zhishu -1 ;
if(p->xishu == 0){
tmp->next = p->next ;
free(p);
p = tmp->next ;
continue ;
}
tmp = p ;
p = p->next ;
}
prt(h);
destroy(h);
}
void prt(linklist h){
linklist p;
p = h->next;
while(p!= NULL){
if(p->xishu < 0){
printf("-");
p->xishu = -p->xishu ;
}
printf("%d",p->xishu);
if(p->zhishu != 0){
printf("X");
if(p->zhishu != 1)
printf("^%d",p->zhishu);
}
p = p->next ;
if(p == NULL)break ;
if(p->xishu > 0){
printf("+");
}
}
}
void destroy(linklist h){
linklist p = h ;
h = h->next ;
while(h != NULL){
free(p);
p = h ;
h = h->next ;
}
free(h);
return ;
}
void input_data(linklist h){
linklist p ,q ;
p = h ;
int num ;
scanf("%d",&num);
getchar();
if(num){
q = (linklist)malloc(sizeof(nodelist));
while((scanf("(%d,%d)",&(q->xishu) ,&(q->zhishu)))!=EOF&& num){
q->next = p->next;
p->next = q ;
p = q ;
num -- ;
if(num == 0)break ;
q = (linklist)malloc(sizeof(nodelist));
}
}
else{
return ;
}
}
void init_list(linklist * h){
*h = NULL ;
*h = (linklist)malloc(sizeof(nodelist));
(*h)->next =NULL ;
}