首页 > 分享 > c语言：养宠物问题

c语言：养宠物问题

萌宠菠菠乐园
2024-11-02 18:25

问题描述：fzk非常喜欢养宠物，比如他现在就养了2头奶牛，3只小熊，4个猩猩，5头大象，还有一个daizi。fzk 把他的宠物关在一些笼子里，例如，fzk当前的分配是：笼子1：奶牛，daizi ；笼子2：奶牛；笼子3：猩猩，大象；笼子4：小熊，猩猩这样总共需要4个笼子。为了节省资金，fzk想用尽可能少的笼子来装下所有宠物。他的办法是在当前的分配下，合并一些笼子。假设每个笼子都足够大，可以装下任意多的宠物，而两个笼子如果装有相同的一种或多种宠物，就可以合并。现在给出fzk当前的分配，你能否帮助fzk算出按照他的方法合并后，总共只需要几个笼子? 比如对于上面的分配，可以合并为：笼子1：奶牛，daizi ；笼子2：猩猩，小熊，大象总共需要2个笼子。
【要求】
【数据输入】首先一个整数t表示测试数据组数（1=<t<=10）。对每组数据，第一行是一个整数k（k>0），表示当前分配下总共的笼子数。在接下来的k行中，每行描述一个笼子中关的宠物。其中第i行的结构是：Ni name1 name2 name3 … nameNi。其中Ni（Ni>0）是该笼子中的宠物的种类数，name1,…,nameNi是这些宠物的种类名称（他们互不相同）。所有的name都是由小写字母组成的字符串，长度不超过10位；所有的Ni之和不超过10000，不同的宠物种类数不超过1000。
【数据输出】对每组测试数据，输出一个整数，表示笼子合并之后fzk可以使用的最少的笼子数。
【样例输入】
1
4
2 nainiu daizi
1 nainiu
2 xingxing daxiang
2 xiaoxiong xingxing
【样例输出】
2

分析：我的想法是假设有四个笼子，将第一个笼子中的宠物与第二三四个笼子中的宠物匹配，如果有相同的，笼子数量减1，并将其他笼子中与笼子一中相同的宠物名置为当前数组中不存在的字符串（当前字符串加上个“he”或其他），保留不同的宠物名，以表示两个笼子合并了。然后再将笼子二与笼子三四匹配，以此类推。
因为要求用c语言来写，并且根据其给出样例的数据输入形式，我选择使用二维字符数组来作为载体。
要注意的是字符数组如果要动态赋值的话要先开辟空间。还有就是不知道为什么我的字符数组未做任何赋值操作时，数组里的值不为’’，而是乱码，这导致后面串匹配无法进行，于是我在初始化数组时直接给每个数组单元赋值为“null”,这样实属为了应付题目的无奈之举，如果大家知道为什么会出现这个问题，希望能告知一声，谢谢！

代码：

#include <stdio.h> #include <string.h> #include <stdlib.h> char *name[100][100];//二维字符输出用来存放宠物 int i,j,m,r; int k,Ni;//n是笼子数，Ni是每个笼子中动物的种类 void input(){//用于输入的函数for(i=0;i<100;i++)for(j=0;j<100;j++){name[i][j]=(char*)malloc(13*sizeof(char));//开辟空间(宠物名长度不超过10，由于我后面还要给某些名字加上“he”表示已合并，所以这里干脆开辟空间13strcpy(name[i][j],"null");}scanf("%d",&k);//输入笼子数for(i=0;i<k;i++){Ni=0;char *str; str=(char*)malloc(13*sizeof(char));scanf("%d",&Ni);//输入宠物种类for(j=0;j<Ni;j++){scanf("%s",str); strcpy(name[i][j],str);}} } int main(){int t=0;//t是输入数据组数while(t<1||t>10){//（1=<t<=10）的约束scanf("%d",&t);}while(t>0){input();for(i=0;i<k;i++){for(m=i+1;m<k+1;m++){for(j=0;strcmp(name[i][j],"null");j++){for(r=0;strcmp(name[m][r],"null");r++){if(strcmp(name[i][j],name[m][r])==0){//如果两个笼子中有相同的动物，就“合并”，笼子数量减1k=k-1;strcpy(name[m][r],strcat(name[m][r],"he"));break;}}}}}printf("%dn",k);//输出笼子数t-=1;}for(i=0;i<100;i++)for(j=0;j<100;j++) free(name[i][j]);//释放空间return 0; }

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859

题目中数据的执行结果：
在这里插入图片描述
其他数据的测试结果（第一行2代表2组数据）

有一点bug，但应付题目中的测试数据，和一些普通的数据还是可以的。写的不太好，望大家包涵。