c语言吧 关注：794,593贴子：4,321,405
求救!!!!!!!!急!!!!
收藏
- 回复
这个问题不错。讨论一下。
VC99已经算出需要的内存数了。280M。这个数字在32位系统里，是很小的。物理内存＋虚拟内存，使得基本上每一个系统都能申请到这么多的内存（C用MALLOC，C++用NEW）。
既然系统支持这么多内存，那我们当然要用空间换取速度，来尽快完成这个问题。
由于每组是14个INT型（4字节），没办法直接进行数学运算（14×4＝56字节，现在32位机子上的编译器，绝大部分都只能支持到8字节64位）。我们应该用另外的方法来实现。
1、我第一反应，就是用二叉树。不过仔细想了想，好像没办法完成。
换思路。用HASH。不过C语言没有系统可用的HASH函数。得自己去找或者自己写一个。我基本上没研究过HASH函数，对这个了解不是很多，不知道有哪些开源库可用。VC99对这个有过研究，可以提供一些吗？8PM对开源库很熟悉，也许也能提供一些帮助。
如果用C++，那就方便了。因为C++提供了HASH函数。在这里用std::map最方便。构造一个：std::map< int, std::map< int, std::map< ...(共14级)>>>>>>>>>>>>>>(我不知道能不能构造成功。呵呵，从来没试过，刚才试了一下，3级的时候，是没问题的)
用HASH，速度就会很有保障。伪代码如下：
（1）、构造14个HASH表（暂时为空）
（2）、读取一组数
（3）、把每一个数放入HASH函数中，在当前HASH表中查询，如果出现过，则按分支继续比较下一个数
（4）、如果没出现过，则在当前HASH表中添加一个新的分枝，并把该组中剩下的数逐个添加到这个分枝中。
（5）、比较完14组，如果都出现过，则对应的HASH值＋1。
2、用链表
这个实现起来比较简单，唯一的缺点是，每次比较的速度会慢一些。伪代码如下：
（1）、构造一个链表，共14级（暂时为空）。链表的结构大致如下：
struct link{
int num;
int times;//计算次数。但是只有最后一级的数字才需要。实际可以构造两种不同的链表。
struct * link same_level;//用于链接当前级别下所有出现的链表。每一个不同的数出现，都要构造一个新链表，并链接上。
struct * link next_level;//用于链接下一级别，这个总共有14级，表示14个数，共一组
};
（2）、读取一组数
（3）、比较每一级数，如果有了，继续比下一级（比起HASH,速度就慢在这里）
（4）、如果没有，则在当前链表下创建一个新的分枝，并把该组下的所有数都放进去。
（5）、比较完14级的数，如果都出现过，则最后一个数的times＋1。表示出现过一次了。
3、用数组
每出现一组不同的数，就malloc一个新的int [14]数组，用来保存这个数。
这些所有的int [14]数组，要用一个链表来链接。链表结构如下：
struct link{
int num[14];
int times;
struct link* next;
}
这个方法比前一种还要慢一些，因为每次都要比较很多很多次数。但更容易实现。好像它需要的内存要比前两个少得多。
4、用大数运算库。
把这14个数看成一个56字节的数，用大数运算库进行比较（或者可以结合HASH，速度会提高一点）。
特点：最容易实现，哈哈，基本上不需要什么脑筋。
但速度……估计……
VC99已经算出需要的内存数了。280M。这个数字在32位系统里，是很小的。物理内存＋虚拟内存，使得基本上每一个系统都能申请到这么多的内存（C用MALLOC，C++用NEW）。
既然系统支持这么多内存，那我们当然要用空间换取速度，来尽快完成这个问题。
由于每组是14个INT型（4字节），没办法直接进行数学运算（14×4＝56字节，现在32位机子上的编译器，绝大部分都只能支持到8字节64位）。我们应该用另外的方法来实现。
1、我第一反应，就是用二叉树。不过仔细想了想，好像没办法完成。
换思路。用HASH。不过C语言没有系统可用的HASH函数。得自己去找或者自己写一个。我基本上没研究过HASH函数，对这个了解不是很多，不知道有哪些开源库可用。VC99对这个有过研究，可以提供一些吗？8PM对开源库很熟悉，也许也能提供一些帮助。
如果用C++，那就方便了。因为C++提供了HASH函数。在这里用std::map最方便。构造一个：std::map< int, std::map< int, std::map< ...(共14级)>>>>>>>>>>>>>>(我不知道能不能构造成功。呵呵，从来没试过，刚才试了一下，3级的时候，是没问题的)
用HASH，速度就会很有保障。伪代码如下：
（1）、构造14个HASH表（暂时为空）
（2）、读取一组数
（3）、把每一个数放入HASH函数中，在当前HASH表中查询，如果出现过，则按分支继续比较下一个数
（4）、如果没出现过，则在当前HASH表中添加一个新的分枝，并把该组中剩下的数逐个添加到这个分枝中。
（5）、比较完14组，如果都出现过，则对应的HASH值＋1。
2、用链表
这个实现起来比较简单，唯一的缺点是，每次比较的速度会慢一些。伪代码如下：
（1）、构造一个链表，共14级（暂时为空）。链表的结构大致如下：
struct link{
int num;
int times;//计算次数。但是只有最后一级的数字才需要。实际可以构造两种不同的链表。
struct * link same_level;//用于链接当前级别下所有出现的链表。每一个不同的数出现，都要构造一个新链表，并链接上。
struct * link next_level;//用于链接下一级别，这个总共有14级，表示14个数，共一组
};
（2）、读取一组数
（3）、比较每一级数，如果有了，继续比下一级（比起HASH,速度就慢在这里）
（4）、如果没有，则在当前链表下创建一个新的分枝，并把该组下的所有数都放进去。
（5）、比较完14级的数，如果都出现过，则最后一个数的times＋1。表示出现过一次了。
3、用数组
每出现一组不同的数，就malloc一个新的int [14]数组，用来保存这个数。
这些所有的int [14]数组，要用一个链表来链接。链表结构如下：
struct link{
int num[14];
int times;
struct link* next;
}
这个方法比前一种还要慢一些，因为每次都要比较很多很多次数。但更容易实现。好像它需要的内存要比前两个少得多。
4、用大数运算库。
把这14个数看成一个56字节的数，用大数运算库进行比较（或者可以结合HASH，速度会提高一点）。
特点：最容易实现，哈哈，基本上不需要什么脑筋。
但速度……估计……
