2015年新疆维吾尔自治区数据理论要领
更新时间:2023-05-19 13:27:01 阅读量: 实用文档 文档下载
- 2015世界杯推荐度:
- 相关推荐
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);
}
main()
{linklist head,p,r;
int n,s,m,i;
printf("n=");
scanf("%d",&n);
printf("s=");
scanf("%d",&s);
printf("m=",&m);
scanf("%d",&m);
if (n<1) printf("n<0");
else
{/*建表*/
head=(linklist)malloc(sizeof(listnode)); /*建第一个结点*/
head->data=n;
r=head;
for (i=n-1;i>0;i--) /*建立剩余n-1个结点*/
{ p=(linklist)malloc(sizeof(listnode));
p->data=i;
p->next=head;
head=p;
}
r->next=head; /*生成循环链表*/
jose(head,s,m); /*调用函数*/
}
}
3、有一个带头结点的单链表,每个结点包括两个域,一个是整型域info,另一个是指向下一个结点的指针域next。假设单链表已建立,设计算法删除单链表中所有重复出现的结点,使得info域相等的结点只保留一个。
#include <stdio.h>
typedef char datatype;
typedef struct node{
datatype data;
struct node * next;
} listnode;
typedef listnode* linklist;
/*--------------------------------------------*/
/* 删除单链表中重复的结点 */
/*-----------------------------------
---------*/
linklist deletelist(linklist head)
{ listnode *p,*s,*q;
p=head->next;
while(p)
{s=p;
q=p->next;
while(q)
if(q->d
2015年新疆维吾尔自治区数据理论要领
ata==p->data)
{s->next=q->next;free(q);
q=s->next;}
else
{ s=q; /*找与P结点值相同的结点*/
q=q->next;
}
p=p->next;
}
return head;
}
正在阅读:
2015年新疆维吾尔自治区数据理论要领05-19
2019北京通州初一(上)期末数学03-05
2019届中考物理模拟试题17 新人教版10-08
2019年整理--校园主题晚会报幕词02-26
2019年入党志愿书填写范文模板03-18
2019思想政治表现评语集锦-范文精品03-05
2019年设备租用合同协议书范本03-15
2019年整理--音乐学院暑假实践报告02-28
2019接待工作方案4篇03-12
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 新疆维吾尔自治区
- 要领
- 理论
- 数据
- 2015
- 高中历史第单元烽火连绵的局部战争单元检测岳麓版选修讲义
- 三角形的内角和练习
- 生物科学与生物工程学院毕业设计(论文)选题原则
- 逻辑函数的公式化简法
- 2014河北政法干警面试指导:人际关系类试题答题技巧
- 爱国主义电影观后感十篇
- Aroma compounds resulting from the acid-catalyzed breakdown of citral
- 工程经济学第4章工程经济评价的基本指标
- 2014生物-血液在心脏血管的循环流动 2
- 新世纪研究生公共英语课后翻译英汉对照
- 先进学校申报材料
- 浅析邮轮设计审美
- 租赁汽车项目方案.doc
- 界面设计复习题及答案
- 未来中国儿童图书行业发展前景分析
- 2007年黑龙江省公务员录用考试《申论》(B)试卷
- 122411111 黄喻嘉 大学四年计划
- 增强民族文化认同感
- Combinatorial rules of icosahedral capsid growth
- 糖尿病周围神经病变与C肽关系的临床观察_芦少敏