2015年新疆维吾尔自治区数据理论要领

1、若第n件物品能放入背包，则问题变为能否再从n-1件物品中选出若干件放入背包（这时背包可放入物品的重量变为s-w[n]）。若第n件物品不能放入背包，则考虑从n-1件物品选若干件放入背包（这时背包可放入物品仍为s）。若最终s=0,则有一解；否则，若s<0或虽然s>0但物品数n<1,则无解。

（1）s-w[n],n-1 //Knap(s-w[n],n-1)=true

（2）s,n-1 // Knap←Knap(s,n-1)

2、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。

#include<stdlib.h>

typedef int datatype;

typedef struct node

{datatype data;

struct node *next;

}listnode;

typedef listnode *linklist;

void jose(linklist head,int s,int m)

{linklist k1,pre,p;

int count=1;

pre=NULL;

k1=head; /*k1为报数的起点*/

while (count!=s) /*找初始报数起点*/

{pre=k1;

k1=k1->next;

count++;

}

while(k1->next!=k1) /*当循环链表中的结点个数大于1时*/

{ p=k1; /*从k1开始报数*/

count=1;

while (count!=m) /*连续数m个结点*/

{ pre=p;

p=p->next;

count++;

}

pre->next=p->next; /*输出该结点，并删除该结点*/

printf("%4d",p->data);

free(p);

k1=pre->next; /*新的报数起点*/

}

printf("%4d",k1->data); /*输出最后一个结点*/

free(k1);

}