电子锁.cpp

某机要部门安装了电子锁。M个工作人员每人发一张磁卡

 
//数据结构课程设计

//我真诚地保证：

//我自己独立地完成了整个程序从分析、设计到编码的所有工作。

//如果在上述过程中,我遇到了什么困难而求教于人,那么，我将在

//程序实习报告中详细地列举我所遇到的问题，以及别人给我的提示。

//在此,我感谢肖罗和邱俊对我的启发和帮助。下面的报告中,我还会

//具体地提到他们在各个方面对我的帮助。

//我的程序中凡是引用到其他程序或文档之处,例如教材、课堂笔记、

//网上的源代码以及其他参考书上的代码段,我都已经在程序的注释里

//很清楚地注明了引用的出处。

//我从未抄袭过别人的程序,也没有盗用别人的程序，但有过修改式的

//抄袭，绝无原封不动的抄袭。

//我编写这个程序,从来没有想过要去破坏或妨碍其他计算机系统的

//正常运转。

//〈谢小欢〉

/*文件名称：电子锁.cpp	

项目名称：电子锁

创建者：谢小欢

创建时间：2006年4月20日

最后修改时间：2006年5月3日

功能：

    某机要部门安装了电子锁。M个工作人员每人发一张磁卡，卡上有开锁的密码特征。

为了确保安全，规定至少要有N个人同时使用各自的磁卡才能将锁打开。 问:                                                             
    
	(1)电子锁上至少要有多少种特征?
    
	(2)每个人的磁卡上至少要有多少种特征?
    
	如果特征的编号以小写英文字母表示,将每个人的磁卡的特征编号打印出来,要求

输出的电子锁的总特征数最少。                                                
    
	设3≤M≤7，1≤N≤4, M与N由键盘输入，工作人员的编号用1＃，2＃,…表示。

文件中的函数名称和简单功能描述: 

combination2: 排列组合,计算一个排列的结果; 

combination1:生成特征码集合序列;

Process:加工处理形成特征码;  

Strcat:缀加字符或数据;

Strcpy:将一个数组中的字符或字符串复制到另一个数组中去;

setsub:移动字符串,提取两个字符串中不同的单元，并把不同的放在字符串中;

main:数据及特征吗的输入输出;  


程序源代码:*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char s2[11][256];//唯一的全局变量,定义字符数组,用来存储特征码值
//运算中的缓冲值
long combination2(int m, int n) {  //函数名: combination2;功能:排列组合,计算一个
	//排列的结果:C(m,n) m个中排列n次
 int n2=n; //定义整型数据n2作临时变量,参与排列组合公式的运算   此函数定义是请教 肖罗 同志的  
           //由网上PASCAL版翻译过来

    if(n>(m / 2)) n2=m-n;

    long c=1;//定义长整型数据C作临时变量,参与排列组合公式的运算

    for(int i=1; i<=n2; i++) {  

        c=c*(m-i+1) / i;     //运用公式计算排列值
    }

    return c;//返回值:当满足前面条件时,根据公式计算出C,并返回C的值

};

int combination1(int n, int r, short * p) { //函数名: combination1;功能:生成特征码集合序列  
	                                  //此函数定义是请教 肖罗 同志的，由网上PASCAL版翻译过来

int i=1;

    for(int j=r; j>0; j--) {
        
        if (p[j]<n+j-r) {  //N+J-R减少的速度慢，p[j]增加的速度更慢，
//多数情况条件成立
           
		    p[j]++;  

            for(int k=j+1; k<=r; k++) p[k] = p[k-1] + 1;   //使得p[]各个单元的值趋向相等 
return i;  

        }
    }

    return 0;

};

char  process(int n, short *p, char a){//函数名:process;功能：加工形成特征码  邱俊同志指教的
	                                 //在s2[p[i]]单元后面缀加n个"a++"和"0"
	char a0[2];
    a++;         //从a的下一个字符开始
	    
    if(a>'z') a='a';//当特征码中的字符不足而需求z后的字符来表示时,特征码跳到
	                //重新由a开始的字符来表示
a0[0] = a;
a0[1] = 0;

    for(int i=1; i<n; i++) {
	
		strcat(s2[p[i]], a0); //每次缀加一个字符
    }

    return a;

};

//  字符串过滤, 将s2中存在的字符从s1中删除, s1剩下的字符串赋给s2
char * setsub(char * s1, char * s2) {  //函数名:setsub; 此函数定义是请教 肖罗 同志的
//功能：提取两个字符串中不同的单元，并把不同的放在字符串中并返回不同的单元组成的串
//定义字符数组指针s1、s2来存储字符
	int n1=strlen(s1);                    
	int n2=strlen(s2);            
	char a[2];
	char s3[256];

	a[1] = 0;
    for(int i=0; i<256; i++) s3[i] = 0; //i,j都为临时循环变量

	for(i=0; i<n1; i++) {
		int f = 0;
	    for(int j=0; j<n2; j++) {
			if(s2[j] == s1[i]) {  //找出两个字符串中相同的单元
		        f = 1;
				break;
	        }
	    }
		if(0 == f) {     //如果没有找到相同的单元，就把字符串中i个单元
//缀加到字符串的末尾上去
			a[0] = s1[i];
			strcat(s3, a);
		}
	}

	strcpy(s2, s3);   //  s2=s3，其中放的是s1,s2中不相同的字符；s1不变

	return s3;

};

int main(int argc, char* argv[]) {

    short p[21];

    int m,n;

    long c1,c2;

    char s1[256];

    printf("输入人员总数M(3<=m<=7), 开锁必需人数N((1<=n<=4)&&(n<m)): ");
    
    do {
		scanf("%d %d", &m,&n);
	    if(m<n) {
		    printf("m小于n，再输入m 和n值");
			//continue;
	    }
		if(m<3 || m>7 || n<1 || n>4) {
			printf("您输入的m和n不在合法的范围之内，再输入m 和n值");
			continue;
		}
		break;
 
	}while(1);    
	
	printf("M=%d, N=%d\n", m, n);

    c1 = combination2(m,n-1);

    c2 = combination2(m-1,n-1); 
    
	printf("特征总数:%d, 每个磁卡特征数:%d\n", c1, c2);

    char a1='a'-1;  //初始值,即a的前一个字符
    
    for(int i=0; i<256; i++) s1[i]=0;

    for(i=0; i<m; i++)
        for(int j=0; j<256; j++)
		    s2[i][j]=0;

    for(i=0; i<c1; i++) {
        a1++;       //在形成特征码时,自加得到下一个字符,从而
		      //特征码得以 a1='a'-1的下一个字符即a开头
	    
		if(a1>'z') a1='a';
	    
		s1[i]=a1;
        
	}

    for(i=1; i<n; i++) {  //数组p中放到n-1的整数
        p[i]=i;   //?????????????????????
    }
    p[n]=m+1;

    i=1;
	a1='a'-1;

    while(i>0) {
        a1 = process(n, p, a1); 
        i = combination1(m,n-1,p);
    }

    for(i=1; i<=m; i++) {
        setsub(s1, s2[i]);
        a1='a'-1;
        printf("%d#   ", i);
        int len = strlen(s2[i]);
        for(int j=0; j<len; j++)
            printf("%c ", s2[i][j]);
        printf("\n");
    }
    
	getchar(); 
	return 0;
}