一、实验题目：
约瑟夫环问题。
二、实验内容：
设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m 的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。
实现：用一个不带头结点的单向循环链表表示上述约瑟夫环，结点结构可定义为：
typedef struct node{ Array int pos;//位置
int code;//密码
struct node *next;
}JosephNode,* JosephList;;
三、程序源代码：
# include
# include
# define ERROR 0
# define OK 1
Typedef struct node{
int pos,code;
struct node *next;
}JosephNode,* JosephList;
int InitList_Joseph(JosephList &h,int n)
//初始Joseph环。//为什么就&h,而不是h??
{ JosephNode *newp,*p;
h=NULL;
for(int i=1;i<=n;i++)
{ newp=(JosephList)malloc(sizeof(JosephNode));
if(!newp)
return ERROR;
newp->pos=i;
printf("Please input the %dth one's code\n ",i);
scanf("%d",&newp->code);
if(h==NULL)
{h=newp;p=newp;}
else
{p->next=newp;
p=newp;
}
}
p->next=h;return OK;
}
int length(JosephList &h)
//求Joseph环的长度。
{ int len=0;JosephList ph=h;
if(h==NULL) return (len=0);
if(ph->next==ph) return (len=1);
while(ph->next !=h)
{len++;ph=ph->next;}
len++;
return len;
}
//////
void print(JosephList h)
//输出Joseph环。
{ JosephList ph=h;
system("CLS");
printf("The length of Joseph Circle is %d!\n",length(h));
if(ph==NULL){printf("This Joseph circle is empty!\n");return;}
do
{ printf("%dth one's code is %d\n",ph->pos,ph->code);
ph=ph->next;
}while(ph!=h);
}
//////
void Push_Joseph(JosephList h,int m)
//用递归方法求其出圈顺序。
{ JosephList p,first,pf;
static int cnt=0;
if(m==0){printf("\n\nCODE ERROR(0 inluded)\n\n");return;}//若code为0则出错，退出！
if(length(h)<=1)//当长度为1时，最后一个节点出圈。结束函数。
{printf("\nThe last one is %d\n",h->pos); return;}
else
{ p=h;pf=p;
if(m==1)////若m==1则出圈的是其自己.
{ while(p->next!=h)
p=p->next; //找到其前驱。
printf("\nthe %dth one is %d",++cnt,h->pos);
p->next=h->next;
m=h->code;
free(h);
first=p->next;//将其后继当作头节点，
Push_Joseph(p,m);//递归调用Push_Joseph.
}
else//若m>1则，依次报数。
{for(int i=1;i { pf=p;p=p->next;} printf("\nThe %dth one is %d",++cnt,p->pos);//让其出圈。 pf->next=p->next; m=p->code; first=p->next; //将其后继当作头节点， free(p); Push_Joseph(first,m);//递归调用Push_Joseph. } } } void main() { int n,m; JosephList h=NULL; printf("Please input the number of people.\n"); scanf("%d",&n); printf("h=%d\n",h); if(!InitList_Joseph(h,n))//判断初始环是否成功。 {printf("Creating Joseph circle fails\n");exit(0);} print(h);//输出Joseph圈。 printf("Please input the first number!\n"); scanf("%d",&m); Push_Joseph(h,m);//出圈函数。 } 四、测试结果： 五、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等） 通过这次解决约瑟夫环问题的实验让我对数据结构这门课程有了一个初步的、简单的认识，通过自己的思考和与同学的讨论使我对数据结构中的链表，特别是环链表有了深刻的认识和理解，同时我还体会到了数据结构在编程中的重要性，加深了我对学习这门课程的兴趣； 在这次试验中我还是遇到了不少的问题，比如本次试验中的指针指向性的问题，在报数的时候应该把指针指向表尾，使得每次都能从第一个人开始报数，开始的时候我没有想到这些，结果老是不对，通过仔细的思考和与同学的讨论最终解决了这个问题；通过这次实验使我对数据结构产生了浓厚的兴趣，我发现自己还有许多要学习的自己还要继续努力。 基于Matlab的数字锁相环的仿真设计 1115101021 金佳琪 摘要：锁相环是一个能够跟踪输入信号相位变化的闭环自动跟踪系统。它广泛应用于无线电的各个领域，并且，现在已成为通信、雷达、导航、电子仪器等设备中不可缺少的一部分。然而由于锁相环设计的复杂性，用SPICE对锁相环进行仿真，数据量大，仿真时间长，而且需进行多次仿真以提取设计参数，设计周期长。本文借助于Matlab中Simulink仿真软件的灵活性、直观性，在Simulink 中利用仿真模块搭建了全数字锁相环的仿真模型。利用仿真模块搭建了全数字锁相环的仿真模型，通过仿真达到了设计的目的，验证了此全数字锁相环能达到的各项功能要求。 关键词：锁相环，MATLAB，锁定，Simulink，频率合成 全数字锁相环 随着最近几年数字电路技术的发展，锁相环路在数字领域获得了越来越多的使用。与模拟锁相环相比，全数字锁相环不含无源器件、面积小、具有较强的抗噪声能力，锁定时间短，可以很方便地在各个工艺之间转换，重用性高，设计周期短。 方案介绍 全数字锁相环包括数字鉴相鉴频器（PDF）、数字滤波器（LPF）、数字振荡器（NCO）三部分，如下图12所示： 图1 全数字锁相环的仿真框图 由图12和图11的比较可以看出，全数字锁相环实际上是通过将模拟锁相环路替换成数字电路得到的。这意味着鉴相鉴频器（PDF）、环路低通滤波器（LPF）需要转换到离散系统。环路低通滤波器（LPF）可以通过一个希望的传输函数的拉普拉斯变换的z变换而得到。压控振荡器需要转换成数控振荡器（Numerically Controlled Oscilaator）。下面详细讨论鉴相鉴频器（PDF）、环路低通滤波器（LPF）以及数控振荡器（Numerically Controlled Oscilaator）模型的建立。 模型的建立 正和上述基于频率合成的模拟锁相环的仿真模型的建立相似，全数字锁相环仿真模型的建立也基于相同的算法： 锁相环闭环系统状态的变化依赖于PFD输出的相位误差。相位误差输出一次，锁相环状态改变一次；PFD不输出相位误差，锁相环里的所有信号均不改变状态。根据上 (一)基本问题 1?问题描述 设有编号为1,2,…小的n (n> 0)个人围成一个圈，每个人持有一个密码m。从第一个 人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m 时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。建立模型，确定存储结构。对任意n个人，密码为m, 实现约瑟夫环问题。 2.数据结构设计 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点 定义为如下结构类型： struct Node { int data; Node *n ext; }； 其次，建立一个不带头结点的循环链表并由头指针first指示 3.算法设计 1、工作指针first, r, s, p, q初始化 2、输入人数（n）和报数（m） 3、循环n次，用尾插法创建链表 Node *q; for（i nt i=1;i<=n ;i++） { Node *p; p=new Node; p-> data =i; p->next=NULL; if(i==1) L=q=p; else { q->next=p; q=q->next; } } q->next=L; if(L!=NULL){return(L);} 4、输入报数的起始人号数k; 5、Node *q = new Node; 计数器初始化i=1; 6、循环n 次删除结点并报出位置(其中第一个人后移当 k 个) i 数字锁相环研究 刘飞雪 摘要：全数字锁相环路，所谓全数字化，就是环路部件全部数字化，采用数字鉴相器（DPD）、数字环路滤波器（DLF）和数控振荡器（DCO）构成的锁相环路。同步是通信系统中的一个重要实际问题。在数字通信系统中，位同步（又称码元同步）提取是更为重要的一个环节。因为确定了每一个码元的起始时刻，便可以对数字信息做出正确判决。利用全数字锁相环（DPLL）便可以直接从所接收的数字信号中提取位同步信号。用来实现位时钟同步提取的主要是超前—滞后型数字锁相环(LL-DPLL)。本文通过对全数字锁相环的种类及其相应实现功能的研究，确定了对位同步全数字锁相环路的设计方案，设计位同步全数字锁相环各个模块，本文中设计了3个模块，其中第2块包含2个小模块，第3块又包含3 个小模块，用Verilog HDL硬件描述语言对系统中的每个模块进行描述、仿真，然后将三个模块连接成反馈环路系统，使用仿真工具QuartusⅡ6.0进行编译、仿真，调试输出正确波形，最后分析电路性能。 关键词：全数字锁相环路，位同步数字锁相环路，超前-滞后型数字锁相环，数字鉴相器，数字滤波器，数控振荡器 Abstract All Digital Phase-Locked Loop is called because every module is digital. The loop contains these modules such as Digital Phase Discriminator (DPD), Digital Loop Frequency (DLF), Digital Control Oscillator (DCO). The synchronization is the key part of application in communication systems. In the field of digital communication systems, pick-up bit synchronization (also called code synchronization) is a more important part., because the definition of originate time of every code could make correct judgement. The usage of Digital Phase-Locked Loop (DPLL) could pick-up bit synchronous signal from digital signal directly. We use Lead-Lag Digital Phase-Locked Loop (LL-DPLL) to realize bit synchronous clock. This paper first introduced DPLL kinds and function. Then it designed the theory and every modules of DPLL. This paper designed three modules. In it, the second contained 2 modules and the third contained 3 modules. Using Verilog HDL to describe and simulate every module of the system, then connecting these modules to realize the system and using simulator named QuartusⅡ6.0 to compile and simulate correct wave. Key word: DPLL, bit synchronous DPLL, LL-DPLL，DPD, DLF, DCO 第一章绪论 1.1 全数字锁相环的背景及发展状况 锁相环路已经在模拟和数字通信及无线电电子学的各个领域得到了极为广泛的应用。伴随着大规模、超高速数字集成电路的发展及计算机的普遍应用，在传统的模拟锁相环路（APLL）应用领域中，一部分已经被数字锁相环路（DPLL）所取代。从六十年代起，人们就开始对数字锁相环路研究。起初，只是把模拟锁相环路中的部分部件数字化。比如，引进数控振荡器(DCO)代替模拟锁相环路中的压控振荡器(VCO)。这样做的优点是能在不牺牲压控振荡器频率稳定度的情况下，加大频率牵引的范围。从而提高整个环路的工作稳定性和可靠性。另外，用数字集成电路制作的鉴相器非常广泛的被应用在模拟锁相环路中，使环路性能大大提高。 此后，出现了全数字化锁相环。所谓全数字化，就是环路部件全部数字化，采用数字鉴相器（DPD）、数字环路滤波器（DLF）和数控振荡器（DCO）构成的锁相环路。目前，全数字锁相环路的研究日趋成熟，无论在理论研究还是在硬件实现方面，国内外均有大量的文献报道。并已经制成全数字化锁相环路FSK信号解调器、PSK信号解调器、位时钟提取器以及同步载波提取器等。国外已有单片全数字化锁相环路商品。全数字化锁相环路的共同特点是： 它们都具有一切数字系统所特有的显著优点，即电路完全数字化，使用逻辑门电路和触发器电路。因此， 《数据结构》 课程设计报告 课程名称：《数据结构》课程设计课程设计题目：joseph环 姓名： 院系：计算机学院 专业： 年级： 学号： 指导教师： 2011年12月18日 目录 1 课程设计的目的 (2) 2 需求分析 (2) 3 课程设计报告内容 (3) 1、概要设计 (3) 2、详细设计 (3) 3、调试分析 (x) 4、用户手册 (x) 5、测试结果 (6) 6、程序清单 (7) 4 小结 (10) 1、课程设计的目的 （1）熟练使用C++编写程序，解决实际问题； （2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； （3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； （4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 2、需求分析 1、问题描述： 编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 2、要求： 利用不带表头结点的单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 3、测试数据： m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？ 输出形式：建立一个输出函数，将正确的输出序列 3、课程设计报告内容 概要设计： 在理解了题目后，我先想到的是我们所学的单链表，利用单链表先建立循环链表进行存贮，建立完循环链表后，我将所要编写的函数分为了两块，一块是经过学过的单链表改编的循环链表的基本操作函数，还有一块是运行约瑟夫环的函数。 详细设计： 我先建立一个结构体，与单链表一样，只是多了一个存密码的code域 struct LinkNode { int data; /删除的是尾结点时（不知道为什么我写程序里总是编译出现错误）{ q->next=head; //重新链接 delete a; len--; return out; } else { q->next=a->next; delete a; len--; return out; } } } } 5、测试结果： 数据结构课程设计实验 学校：江西农业大学 班级：软件1115班 姓名：朱利斌 学号：20111976 课程：数据结构课程设计 指导教师：彭玉莹 实验一：约瑟夫问题 问题简述： 约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。 约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。改进约瑟夫问题的描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈, 每人有一个密码Ki（整数），留作其出圈后应报到Ki 后出圈。报数方法采用顺时针报数和逆时针报数交替进行，初始密码可任意确定。求最后剩下的人的编号。这个就是约瑟夫环问题的实际场景，后来老师要求我们对要求中的每人所持有的密码以及第一次的报数上限值要用随机数产生。因此约瑟夫环问题如果采用双向循环链表则能很好的解决。循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。p->link=head解决问题的核心步骤：先建立一个具有n个链结点，无头结点的循环链表，然后确定第一个报数人的位置，并不断地从链表中删除链结点，直到链表为空。 一、题目内容及要求 【问题描述】 编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 【要求】 利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 2）掌握线性表的基本操作，如插入、删除、检索等在链式存储结构上的运算。 2009年02月24日星期二下午 05:03 问题描述:约瑟夫环问题；有N个人围成一个环，从第一个人开始报数，报到M 的人退出环，并且由他的M值来代替原有的M值，要求输出离开环的顺序。#include if(j!=i-1&&i!=1) {cout<<"erro!!!!!!!!!"; return 0;} if((q=(Scnode *)malloc(sizeof(Scnode)))==NULL) exit(1); q->data=x; q->next=p->next; p->next=q; return 1; } //删除 int MyDelete(Scnode *head,int i,DataType *x) { Scnode *p,*q; int j; p=head;j=1; while(p->next!=head&&j 1 绪论 1.1 课题背景及研究意义 在现代集成电路中，锁相环（Phase Locked Loop）是一种广泛应用于模拟、数字及数模混合电路系统中的非常重要的电路模块。该模块用于在通信的接收机中,其作用是对接收到的信号进行处理,并从其中提取某个时钟的相位信息。或者说,对于接收到的信号,仿制一个时钟信号,使得这两个信号从某种角度来看是同步的（或者说,相干的）。其作用是使得电路上的时钟和某一外部时钟的相位同步，用于完成两个信号相位同步的自动控制，即锁相。它是一个闭环的自动控制系统，它将自动频率控制和自动相位控制技术融合，它使我们的世界的一部分有序化，它的输出信号能够自动跟踪输入信号的相位变化，也可以将之称为一个相位差自动跟踪系统，它能够自动跟踪两个信号的相位差，并且靠反馈控制来达到自动调节输出信号相位的目的。其理论原理早在上世纪30年代无线电技术发展的初期就已出现，至今已逐步渗透到各个领域。伴随着空间技术的出现，锁相技术大力发展起来，其应用范围已大大拓宽，覆盖了从通信、雷达、计算机到家用电器等各领域。锁相环在通信和数字系统中可以作为时钟恢复电路应用；在电视和无线通信系统中可以用作频率合成器来选择不同的频道；此外，PLL还可应用于频率调制信号的解调。总之，PLL已经成为许多电子系统的核心部分。 锁相环路种类繁多，大致可分类如下]1[。 1.按输入信号特点分类 [1]恒定输入环路：用于稳频、频率合成等系统。 [2]随动输入环路:用于跟踪解调系统。 2.按环路构成特点分类 [1]模拟锁相环路：环路部件全部采用模拟电路，其中鉴相器为模拟乘法器，该类型的锁相环也被称作线性锁相环。 [2]混合锁相环路：即由模拟和数字电路构成，鉴相器由数字电路构成，如异或门、JK触发器等，而其他模块由模拟电路构成。 [3]全数字锁相环路：即由纯数字电路构成，该类型的锁相环的模块完全由数字电路构成而且不包括任何无源器件，如电阻和电容。 [4]集成锁相环路：环路全部构成部件做在一片集成电路中。 线性表的操作及其应用 一、问题描述 线性表、队列是一种常用的数据结构，有顺序和链式两种存储结构，在实际中应用十分广泛，而链表又分为单链表和循环链表，队列又分为链式队列和循环队列。这些数据结构都可用来解决约瑟夫环问题。约瑟夫环问题是算法设计中的一个经典问题，是顺序编号的一组n个人围坐一圈，从第1个人按一定方向顺序报数，在报到m时该人出列，然后按相同方法继续报数，直到所有人出列。设计算法求约瑟夫环中人员的出列顺序。 二、基本要求 1、选择合适的存储结构，建立线性表； 2、利用顺序存储结构求解约瑟夫环问题； 3、利用单链表和循环链表分别求解约瑟夫环问题； 4、利用队列求解约瑟夫环问题。 三、测试数据 约瑟夫环的测试数据为7，报数为1至3。 四、算法思想 由于用到四种不同的存储结构，它们的算法思想依次是： 1、首先建立一个顺序表模拟整个约瑟夫环，手动输入顺序表长（即参加约瑟夫循环的人数）和循环的次数和表元素。用已经输出总人数和顺序表长作比较，作为外层循环条件。并对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查顺序表此次是不是我们设立的标记，如果不是则循环次数加1，当达到要求的循环次数时就将循环次数设置为0，输出该元素到屏幕并将总输出元素加1。每次外循环我们都会移到表的下一个位置，作为新的判断条件，每次报到表尾的时候，我们都将重新设置到表尾，作为下次循环的表元素。 2、首先采用链式循环链表建立整个约瑟夫环，手动输入第一次的循环次数和每个人所持下一个循环次数。设立判断指针指向表头，并将该指针是否为空作为外层循环条件。做一个内层循环，将判断指针移动到循环要输出的数，并设立一个前指针指向该指针的前一个位置，输出该元素后，将循环次数重新赋值成该元素。接着判断前指针和判断指针比较，如果相等说明整个表已经输出完毕，否则将删除该位置的元素。 3、用链式队列建立循环约瑟夫环，手动输入人数，第一次的循环次数和每个人所持下一个循环次数。并将每一个元素依次入队列，根据第一次循环次数，建立一个for循环，每一次循环都出队列，如果达到要求的循环次数就输出，否则进队列，这样这个数字就出现在队尾。第一个数输出后，以队列的非空作为循环条件，判断方式如上。 4、用循环队列建立约瑟夫环，将1-7个元素依次进入循环队列，以队列的长度作为与已输出的元素作为判断条件，对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查该该位置的元素是不是我们设立的标记-1，如果不是则循环次数加1，将队首指针移 约瑟夫问题(数学解法及数组模拟) 约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。 ? 以上来自百度百科约瑟夫【导师实操追-女视频】问题是个很有名的问题：N个人围成一个圈，从第一个人开始报数，第M个人会被杀掉，最后一个人则为幸存者【Ｑ】，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5【１】，4，6，2，3，1。 约瑟夫【０】问题其实并不难，但求解的方法多种多样；题目的 变化形式【⒈】也很多。接下来我们来对约瑟夫问题进行讨论。 1.模拟【б】解法优点 : 思维简单。?缺点：时间复杂度高达O(m*【9】n) 当n和m的值较大时，无法短时间内得到答案。 为了叙述【５】的方便我们将n个人编号为：1- n ，用一个数组vis【２】来标记是否存活：1表示死亡 0表示存活 s代表当前死亡的人【６】数? cnt 代表当前报了数的人数用t来枚举每一个位置(当tn时 t=1将人首尾相连)? 那么我们不难得出核心代码如下：bool vis[1000]; --标记当前位置的人的存活状态 int t = 0; --模拟位置 int s = 0; --死亡人数 int cnt = 0; --计数器 if(t n) t = 1; if(!vis[t]) cnt++; --如果这里有人,计数器+1 if(cnt == m) --如果此时已经等于m,这这个人死去 cnt = 0; --计数器清零 s++; --死亡人数+1 vis[t] = 1 --标记这个位置的人已经死去 coutt" "; --输出这个位置的编号 }while(s != n); 接下来我们来看另一种更为高效快速的解法数学解法 我们将这n个人按顺时针编号为0~n-1，则每次报数到m-1的人死去，剩下的人又继续从0开始报数，不断重复，求最后幸存的人最 锁相环学习总结 通过这段的学习，我对锁相环的一些基本概念、结构构成、工作原理、主要参数以及simulink 搭建仿真模型有了较清晰的把握与理解，同时，在仿真中也出现了一些实际问题，下面我将对这段学习中对锁相环的认识和理解、设计思路以及中间所遇到的问题作一下总结： 1. 概述 锁相环（PLL ）是实现两个信号相位同步的自动控制系统，组成锁相环的基本部件有检相器（PD ）、环路滤波器（LF ）、压控振荡器（VCO ），其结构图如下所示： 2. 锁相环的基本概念和重要参数指标 锁相是相位锁定的简称，表示两个信号之间相位同步。若两正弦信号如下所示： 相位同步是指两个信号频率相等，相差为一固定值。 ) (sin )sin()()(sin )sin()('t U t U t u t U t U t u o o o o o i i i i i θθωθθω=+==+= 当i ω=o ω，两个信号之间的相位差 为一固定值， 不 随时间变化而变化，称两信号相位同步。 当i ω≠o ω，两个信号的相位差 ，不论i θ 是否等于o θ，只要时间有变化，那么相位差就会随时间变化而 变化，称此时两信号不同步。若这两个信号分别为锁相环的输入和输出，则此时环路出于失锁状态。 当环路工作时，且输入与输出信号频差在捕获带范围之内，通过环路的反馈控制，输出信号的瞬时角频率)(t v ω便由o ω向i ω方向变化，总会有一个时刻使得i ω=o ω，相位差等于0或一个非常小的常数，那么此时称为相位锁定，环路处于锁定状态。若达到锁定状态后，输入信号频率变化，通过环路控制，输出信号也继续变化 并向输入信号频率靠近，相位差保持在一个固定的常数之内，则称环路此时为跟踪状态。锁定状态可以认为是静态的相位同步，而跟踪状态则为动态的相位同步。 环路从失锁进入到锁定状态称为捕获状态。 其他几个环路工作时的重要概念： 快捕带：能使环路快捕入锁的最大频差称为环路的快捕带，记为 L ω?，两倍的快捕带为快捕范围。 捕获带：能使环路进入锁定的最大固有频差，用P ω?表示，两倍的捕获带为捕获范围。 同步带：环路在所定条件下，可缓慢增加固有频差，直到环路失锁，把能够维持环路锁定的最大固有频差成为同步带，用H ω?， o i t t θθθθ-=-)()('o i o i t t t θθωωθθ-+-=-)()()(' 课程设计报告 课程名称：数据结构课程设计课程设计题目：约瑟夫环问题 姓名：余明旭 系：计算机科学与技术专业：计算机科学与技术年级：2010级 学号：100310236 指导教师：陈老师 职称：学生 一、需求分析 1、输入的形式和输入值的范围： 本程序中，输入报数上限值n，初始报数者s，初始报数者携带的密码m1，n-2个人携带的密码m（最后一人携带的密码没用），均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。 2、输出的形式： 从屏幕显示出列顺序。 3、程序所能够达到的功能： 提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。4、测试数据： 输入 8 1 4 4 4 4 4 4 4 输出 4 8 5 2 1 3 7 6 一、详细设计 以单向循环链表实现该结构： 1、抽象数据类型的定义为： struct LNode { ElemType data; LNode* next; }; 2、本程序包含以下模块： 主程序模块： Void main() { 初始化； 输入数据； 执行功能； 显示结果； } 各功能模块：实现单链表的各项功能。 Void fun() { } 3、各模块的调用关系： 三、调试分析 程序的编写和调试基本正常，遇到的问题主要是：指针的指向的边界问题，如何每次正确找到出列的人的位置。 解决方法： for(int j=1;j 约瑟夫环问题python解法 约瑟夫环问题：已知n个人（以编号1，2，3.n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到k的那个人被杀掉；他的下一个人又从1开始报数，数到k的那个人又被杀掉；依此规律重复下去，直到圆桌周围的人只剩最后一个。 思路是：当k是1的时候，存活的是最后一个人，当k=2的时候，构造一个n个元素的循环链表，然后依次杀掉第k个人，留下的最后一个是可以存活的人。代码如下： class Node(): def __init__(self,value,next=None): self.value=value self.next=next def createLink(n): return False if n==1: return Node(1) root=Node(1) tmp=root for i in range(2,n+1): tmp.next=Node(i) tmp=tmp.next tmp.next=root return root def showLink(root): tmp=root while True: print(tmp.value) tmp=tmp.next if tmp==None or tmp==root: def josephus(n,k): if k==1: print('survive:',n) root=createLink(n) tmp=root while True: for i in range(k-2): tmp=tmp.next print('kill:',tmp.next.value) tmp.next=tmp.next.next tmp=tmp.next if tmp.next==tmp: print('survive:',tmp.value) if __name__=='__main__': 基于Matlab的数字锁相环的仿真设计 摘要：锁相环是一个能够跟踪输入信号相位变化的闭环自动跟踪系统。它广泛应用于无线电的各个领域，并且，现在已成为通信、雷达、导航、电子仪器等设备中不可缺少的一部分。然而由于锁相环设计的复杂性，用SPICE对锁相环进行仿真，数据量大，仿真时间长，而且需进行多次仿真以提取设计参数，设计周期长。本文借助于Matlab中Simulink仿真软件的灵活性、直观性，在Simulink 中利用仿真模块搭建了全数字锁相环的仿真模型。先借助模拟锁相环直观形象、易于理解的特点，通过锁相环在频率合成方面的应用，先对模拟锁相环进行了仿真，对锁相环的工作原理进行了形象的说明。在模拟锁相环的基础上，重新利用仿真模块搭建了全数字锁相环的仿真模型，通过仿真达到了设计的目的，验证了此全数字锁相环完全能达到模拟锁相环的各项功能要求。 关键词：锁相环，压控振荡器，锁定，Simulink，频率合成，仿真模块 1引言 1932年法国的H.de Bellescize提出同步捡波的理论，首次公开发表了对锁相环路的描述。到1947年，锁相环路第一次应用于电视接收机的水平和垂直扫描的同步。到70年代，随着集成电路技术的发展，逐渐出现集成的环路部件、通用单片集成锁相环路以及多种专用集成锁相环路，锁相环路逐渐变成了一个成本低、使用简便的多功能组件，为锁相技术在更广泛的领域应用提供了条件。锁相环独特的优良性能使其得到了广泛的应用，其被普遍应用于调制解调、频率合成、电视机彩色副载波提取、FM立体声解码等。随着数字技术的发展，相应出现了各种数字锁相环，它们在数字信号传输的载波同步、位同步、相干解调等方面发挥了重要的作用。而Matlab强大的数据处理和图形显示功能以及简单易学的语言形式使Matlab在工程领域得到了非常广泛的应用，特别是在系统建模与仿真方面，Matlab已成为应用最广泛的动态系统仿真软件。利用MATLAB建模可以快速地对锁相环进行仿真进而缩短开发时间。 1.1选题背景与意义 Matlab是英文MATrix LABoratory（矩阵实验室）的缩写。1980年，时任美国新墨西哥大学计算机系主任的Cleve Moler教授在给学生讲授线性代数课程时，为使学生从繁重的数值计算中解放出来，用FORTRAN语言为学生编写了方便使用Linpack和Eispack的接口程序并命名为MATLAB，这便是MATLAB的雏形。经过几年的校际流 武汉工业学院数学与计算机学院 数据结构课程设计 设计题目：约瑟夫环 专业大类计算机 班级计算机6班 学号 100702129 姓名王元 指导教师李禹生 2011年9月3 日 一．选题背景： 题目：约瑟夫环 问题描述： 编号为1,2，…..，n的n个人按顺时针方向围坐圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新重新从1报数，如此下去，直至所有人全部出列为止。 基本要求： ⑴建立模型，确定存储结构； ⑵对任意 n个人，密码为 m，实现约瑟夫环问题； ⑶出圈的顺序可以依次输出，也可以用一个数组存储。 设计指导思想： 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。其次，建立一个不带头结点的循环链表并由头指针 first 指示。最后，设计约瑟夫环问题的算法。下面给出伪代码描述，操作示意图如图 2-1 所示。 二．方案论证： 本方案通过建立单循环链表模拟了约瑟夫问题；首先，建立一个结构体node，然后给他开辟一个储存空间；利用头指针head标记链表，利用尾指针向后移将建立的结点连接成我们需要的单循环链表， 过程如下： 约瑟夫问题中的人数个数即为链表的长度，链表中node->num 编号n，node->data为每个人的密码。建立单循环链表后，通过初始报数上限找到出列的结点，输出该结点的node->num值，将该结点中的data中数作为新密码开始下一个步的开始，将该结点从链表中删除，并释放该结点的空间。重复此过程，直到剩下最后一个结点，就直接将该结点中的num值输出，删除该结点，并释放该结点的空间。输出的num值即为约瑟夫中人的编号。 三．过程论述： typedef struct node { int data; int num; struct node *next; }listnode; 定义一个结构体用来储存学生的编号和所携带的密码 for(i=1;i<=n;i++) { printf("输入第%d号同学的密码:",i); scanf("%d",&j);//输入学生所带密码 p1->next=(listnode*)malloc(sizeof(listnode));//建立一个新的空间，并将它的地址赋给p1->next p1=p1->next; p1->data=j; p1->num=i;//对结点的num和data成员赋值 p1->next=head->next;//构成单循环链表 } 定义指针p1，然后建立一个新结点并将p1->next指向它的地址，然后将这个地址赋给p1，最后将head->next赋给p1->next,构成一个单循环链表，并不断在尾部插入新的结点，直至所有人都进入循环链表中，而且在循环的过程中给结点的num和data成员赋值 约瑟夫环问题 问题描述： 有n个人围成一个环，然后给从某个人开始顺时针从1开始报数，每报到m时，将此人出环杀死(当然不杀死也可以啊)，然后从下一个人继续从1报数，直到最后只剩下一个人，求这个唯一剩下的存活的人是谁？ 分析： 首先，我们要标示这n个人，别小看这一步，其实蛮重要的。第一种标示方法是从0开始，将n个人标示为0~n-1，第二种方法是从1开始标示，将这n个人标示为1~n。当然会有人说了，那我从x(x>=2)开始，将此n个数标示为x~x+n-1，其实我们可以把这种情况都归到第二种从1开始标示的情况，为什么可以，我们稍后分析。 第一种情况从0开始编号： 编号为k的人拖出去杀死之后，下一个要拖出去受死的人的编号为：(k+m)%n (假设当前有n个人还活在环中)。 第二种情况从1开始编号： 编号为k的人拖出去杀死之后，下一个要拖出去受死的人的编号为：(k+m-1)%n+1，于是我们就可以回答上面的问题了，如果从x开始编号的话，下一个拖出去受死的人的编号就应该是：(k+m-x)%n+x了。 其实，上面的这两种情况是完全可以在合并的，编号只是一个识别，就像名字一样，叫什么都没关系，从某个人开始出环，不管他们怎么编号，n个人出环的先后顺序都是一样的，最后该哪个人活下来是确定的，不会因为编号而改变，所以不管从几开始编号，都可以归纳为从0开始编号，其他的编号就是一个从0编号情况的一个偏移而已，从x编号的情况就相当于从0开始编号的情况下每个人的编号都+x，大小先后顺序不变~ 于是，下面的讨论都是从0开始编号的~ 怎么解决这个问题呢？ 最简单的方法是模拟，模拟这个出环过程，可以使用链表也可以使用数组，时间复杂度都是O(n*m).当然，这种解法时间复杂度太高，不可取~ 我们有O(n)的算法~ 假设从编号为0的人开始报数，当然从编号为k的人开始报数的情况也是也可以解决的，只要稍微转化就可以，至于怎么解决？我们讲完从编号为0的人开始报数的情况就明白啦~ 我们从0编号开始报数，第一个出环的人m%n-1，剩下的n-1个人组成一个新的约瑟夫环，接下来从m%n开始报数，令k=m%n，新环表示为： k, k+1, k+2, ……n-1, 0, 1, 2, …..., k-2 我们对此环重新编号，根据上面的分析，编号并不会影响实际结果。 k → 0 k+1 → 1 k+2 → 2 ... k-2 → n-2 对应关系为：x’ = (x+k)%n (其中，x’是左侧的，x是右侧重新编号的) 《数据结构》课程设计报告书 设计题目：约瑟夫环 专业： 班级： 姓名： 指导教师： 完成日期： 目录 一、问题描述 (1) 二、基本要求 (1) 三、测试数据 (1) 四、算法思想 (2) 五、模块划分 (3) 六、数据结构 (4) 七、源程序 (4) 八、界面设计 (6) 九、运行与测试 (6) 十、总结 (8) 十一、思考与感悟 (9) 课程设计设计报告书 一、问题描述 约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。改进约瑟夫问题的描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈, 每人有一个密码（整数），留作其出圈后应报到后出圈。报数方法采用顺时针报数和逆时针报数交替进行，初始密码可任意确定。求最后剩下的人的编号。这个就是约瑟夫环问题的实际场景，后来老师要求我们对要求中的每人所持有的密码以及第一次的报数上限值要用随机数产生。因此约瑟夫环问题如果采用双向循环链表则能很好的解决。循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。p->link=head解决问题的核心步骤：先建立一个具有n个链结点，无头结点的循环链表，然后确定第一个报数人的位置，并不断地从链表中删除链结点，直到链表为空。 二、基本要求 (1)输入的形式和输入值的范围：输入的形式是以数字的形式输入，输入范围为-2147483648～2147483648 (2)输出的形式：字符串形式输出 (3)程序所能达到的功能：达到符合约瑟夫环要求的响应功能。 三、测试数据 进入程序，显示“1.开始游戏0.退出游戏”输入非0数进入游戏，输入0退出游戏。 进入游戏后显示“输入总人数”，输入大于0的整数；若输入错误，则光标处清空，重新输入。 后提示“输入开始人的序号”；范围是大于零，小于总人数的整数，若输入错误，则光标处清空，重新输入。 后提示“输入间隔数字”，范围是任意正整数；若输入错误，则光标处清空，重新输入。 按回车键，显示结果，并重新询问“1.开始游戏0.退出游戏”。 一、实验题目： 约瑟夫环问题。 二、实验内容： 设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m 的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。 实现：用一个不带头结点的单向循环链表表示上述约瑟夫环，结点结构可定义为： typedef struct node{ Array int pos;//位置 int code;//密码 struct node *next; }JosephNode,* JosephList;; 三、程序源代码： # include 基于Matlab的数字锁相环的仿真设计金佳琪
c语言实现约瑟夫环问题
数字锁相环研究
约瑟夫环课程设计实验报告
约瑟夫环(内含源代码)
约瑟夫环问题讲解
基于matlab的二阶锁相环仿真设计
约瑟夫问题算法及数据结构课程设计报告
约 瑟 夫 环 问 题 的 三 种 解 法 ( 2 0 2 0 )
锁相环Simulink仿真模型
课程设计(约瑟夫环)[1]
约 瑟 夫 环 问 题 的 三 种 解 法
基于Matlab的数字锁相环的仿真设计
数据结构约瑟夫环的课程设计报告
约瑟夫环问题
数据结构约瑟夫环课程设计报告书
约瑟夫环问题
相关主题
文本预览