| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4223 人关注过本帖
标题:33 选 7
只看楼主 加入收藏
kai
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:52
帖 子:3450
专家分:59
注 册:2004-4-25
结帖率:100%
收藏
 问题点数:0 回复次数:101 
33 选 7
程序如下, 没有用读文件的方法, 只是将vector中的数据类型设置为char, 这样就节省了3/4的空间

符合 33 选 7 的题意的解仅有31组,程序运行完毕会生成一个 result.dat 文件。

我用学校给我的笔记本电脑运行, 运行时间大约为4分钟,没有超过5分钟

当然那台笔记本电脑的性能是很好的。

那台笔记本电脑的配置为:

Prozessor    x86 Family 6 Model 13 Stepping 6 GenuineIntel 1600MHz

总共 real memory  512MB

可使用的 real memory 225.79MB

总共 virtuell memory 2.00GB

可使用的  virtuell memory 1.96GB



我本来想上传那个 exe 文件的,可惜没有成功,如果要,可以通过Email 发给你。



题目详情请见下面的连接

http://bbs.



#include <iostream>

#include <cstdlib>

#include <algorithm>

#include <vector>

#include <fstream>

using namespace std;



class ChooseNums;



class Item

{

    friend class ChooseNums;

private:

    vector<char> item;

public:

    Item(char c)

    {

        item.push_back(c);

    }

    vector<char> getMe()

    {

        return item;

    }

    bool add(char c)

    {

        if( find(item.begin(), item.end(), c) == item.end())

        {

            item.push_back(c);

            return true;

        }

        return false;

    }

    void sortItem()

    {

        sort(item.begin(), item.end());

    }

    bool equals(const Item & i)

    {

        return equal(item.begin(), item.end(), i.item.begin());

    }

    void display()

    {

        for(int i = 0; i<item.size(); i++)

        {

            cout<<(int)item[i]<<"  ";

        }

        cout<<endl;

    }

};



class ChooseNums

{

private:

    char * source;

    int size;

    int amount;

    vector<Item> temp;

    vector<Item> result;

public:

    ChooseNums(int top, int amount)

    {

        size = top;

        source = new char[size];

        for(int i = 0; i<size; i++)

        {

            source[i] = (char)(i+1);

            Item item(source[i]);

            result.push_back(item);

        }

        this->amount = amount;

    }

    void addIntoTemp(Item & item)

    {

        bool alreadyExist = false;

        for(int i = 0; i<temp.size(); i++)

        {

            if(item.equals((Item)temp[i]))

            {

                alreadyExist = true;

                break;

            }

        }

        if(!alreadyExist)

            temp.push_back(item);

    }

    bool inclusive(const Item & it)

    {

        int cnt = 0;

        bool included = false;

        for(int i = 0; i<temp.size(); i++)

        {

            Item itemTemp = temp[i];

            cnt = 0;

            for(int j = 0; j<it.item.size(); j++)

            {

                char c = it.item[j];

                for(int k = 0; k<itemTemp.item.size(); k++)

                {

                    if(c == itemTemp.item[k])

                        cnt++;

                    if(cnt == 3)

                    {

              
         included = true;

                        break;

                    }

                }

                if(included == true)

                    break;

            }

            if(included == true)

                break;

        }

        return included;

    }

    void chooseNums()

    {

        for(int i = 0; i<amount-1; i++)

        {

            if(i>=2)   //ab level 3

            {

                for(int j = 0; j<result.size(); j++)

                {

                    // get a item from item

                    Item item = result[j];

              
     // check whether it is already inclusive in
the temp vector

                    // if not inclusive

                    if(!inclusive(item))

                    {

              
         // then we try add an new
element

              
         for(int k = 0; k<size;
k++)

                        {

              
             Item
tempItem = item;

              
           
 if(tempItem.add(source[k]))

              
             {

              
           
     // we must check it again, whether there are
three

              
           
     // same numbers

              
           
     // if this is really a new item

              
           
     if(!inclusive(tempItem))

              
           
     {

              
           
         // then we sort it

              
           
         tempItem.sortItem();

              
           
         // and add it into the temp
vector

              
           
         addIntoTemp(tempItem);

              
           
         break;

              
           
     }

              
             }

              
         }   

                    }

                }

            }

            else

            {

                for(int j = 0; j<result.size(); j++)

                {

                    Item item = result[j];

                    for(int k = 0; k<size; k++)

                    {

              
         Item tempItem = item;

              
         if(tempItem.add(source[k]))

                        {

              
           
 tempItem.sortItem();

              
           
 addIntoTemp(tempItem);

                        }

                    }

                }

            }

            

            result = temp;

            temp.clear();

        }

    }

    void writeToFile(char * filename)

    {

        ofstream fout(filename);

        if(!fout.is_open())

        {

            cerr<<"File Open Error\n";

            exit(EXIT_FAILURE);

        }

        int sizeofResult = result.size();

        for(int i = 0; i<sizeofResult; i++)

        {

            Item itemR = result[i];

            vector<char> item = itemR.getMe();

            for(int j = 0; j<item.size(); j++)

            {

                fout<<(int)(item[j])<<"  ";

            }

            fout<<endl;

        }

        fout<<"There are total "<<sizeofResult<<" items"<<endl;

        fout.clear();

        fout.close();

    }

    ~ChooseNums()

    {

        delete [] source;

        size = 0;

        amount = 0;

    }

    void displayResult()

    {

        for(int i =0; i<result.size(); i++)

        {

            Item item = result[i];

            item.display();

        }

    }

};



int main()

{

 // 如果设置参数为6  4 的话,只有3组解:<1 2 3 4> <1 2 5 6> <3 4 5 6>



    ChooseNums cn(33, 7);     

    cn.chooseNums();

    cn.displayResult();

    cn.writeToFile("result.dat");

    system("pause");

    return 0;

}
搜索更多相关主题的帖子: 笔记本电脑 memory 
2005-09-14 00:27
russilong
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2005-8-23
收藏
得分:0 
顶一下。 russilong@yahoo.com.cn

2005-09-14 09:12
Knocker
Rank: 8Rank: 8
等 级:贵宾
威 望:47
帖 子:10454
专家分:603
注 册:2004-6-1
收藏
得分:0 
[QUOTE]符合 33 选 7 的题意的解仅有31组,程序运行完毕会生成一个 result.dat 文件。[/QUOTE]

1.你的结果肯定是错的,符合33 选 7 且 无4连号及4连号以上 的解有  4244643 组.


2.我运行了你的程序 37 分钟未见结果 _^_,只好 kill it.

 环境: PII 300 +  内存 160 M + win me  

结论:写程序的人不能用好电脑,否则会误事的


九洲方除百尺冰,映秀又遭蛮牛耕。汽笛嘶鸣国旗半,哀伤尽处是重生。     -老K
治国就是治吏。礼义廉耻,国之四维。四维不张,国之不国。   -毛泽东
2005-09-14 11:38
kai
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:52
帖 子:3450
专家分:59
注 册:2004-4-25
收藏
得分:0 
knocker, 你注意一下题目的限制条件,下一组与前面各组相比较不可以有相同的3个数出现,正是这个限制条件,所以产生的最后结果我认为是合理的。你看看程序的算法和程序本身,我已经尽可能的让程序简单和高效了,可以用STL的就用STL。 你可以用6 4 或 10 5 这样小数字来测试结果,如果在测试结果中你能想出漏掉了什么解,请你告诉我。 比如用6 4 来测试,结果为3组:<1 2 3 4> <1 2 5 6> <3 4 5 6> 请问漏掉了哪一组解? 用9 5 测试,结果还是3组<1 2 3 4 5> <1 2 6 7 8> <3 4 7 8 9> 用9 7 测试,结果只有1组<1 2 3 4 5 6 7> 到这里大家应该看到一个值得让人注意的地方了。 对于9 7的测试, 结果只有1组是对的,但是为哪一组,确实先入为主的问题,也就是说,如果你选了1 2 3 4 5 6 7为第一组,那么这一组以后,再也找不到其他组合的可能了。 但是如果你说第一组为 2 3 4 5 6 78,那也是对的,从这一组之后,你同样也找不到其余组合的可能了。 这个程序大家还是测试一下,告诉我一声大家所用的时间,如果有死机的也告诉我一声。

自由,民主,平等,博爱,进步.
中华民国,我的祖国,中华民国万岁!中华民国加油!
本人自愿加入中国国民党,为人的自由性,独立性和平等性而奋斗!
2005-09-14 16:22
kai
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:52
帖 子:3450
专家分:59
注 册:2004-4-25
收藏
得分:0 
如果看了上面的帖子还有问题,那我们就来做下面的讨论。
我先问Knocker, 对于10 选 7 会有多少种组合, 你大概会告诉我一个比较大的数字。

那我们就来试试,
我说第一组为       1   2  3   4   5   6   7
从这组之后,你来告诉我,你还能找到其他组吗?如果能?请你告诉我什么.

当然你可以告诉我, 我第一组可以选别的数啊, 当然可以, 比如  2  3  4  5 6  7  8, 然后呢, 然后你同样也找不出其他组合的可能了, 也就是说, 对于10选7 符合题意的解只有1组,确切的讲, 组合数为1.

如果上面的说法你认同的话, 那么33选7的解就是31组, 注意,我说的是31组, 不论你用哪一组作为起始组, 都只能相继产生其他的30组组合.

自由,民主,平等,博爱,进步.
中华民国,我的祖国,中华民国万岁!中华民国加油!
本人自愿加入中国国民党,为人的自由性,独立性和平等性而奋斗!
2005-09-14 16:40
Knocker
Rank: 8Rank: 8
等 级:贵宾
威 望:47
帖 子:10454
专家分:603
注 册:2004-6-1
收藏
得分:0 
[QUOTE]你注意一下题目的限制条件,下一组与前面各组相比较不可以有相同的3个数出现,[/QUOTE] 唉,所以我在JAVA版说过,项目开发时间为什么会拉得这么长?其原因就是客户与程序员之间沟通有问题。 你理解错了,他的要求是:同一组号码不得出现4连号及4连号以上的连号,而不是你说的"下一组与前面各组相比较不可以有相同的3个数". 我想到现在你还不理解楼主的目的或者说你根本不知道33选7是什么

九洲方除百尺冰,映秀又遭蛮牛耕。汽笛嘶鸣国旗半,哀伤尽处是重生。     -老K
治国就是治吏。礼义廉耻,国之四维。四维不张,国之不国。   -毛泽东
2005-09-14 20:20
Knocker
Rank: 8Rank: 8
等 级:贵宾
威 望:47
帖 子:10454
专家分:603
注 册:2004-6-1
收藏
得分:0 
这么说吧,33选7的号码组合全集是 4272048 组。这个完全可以计算的。我保证没错。 楼主的原先的要求是他自己设置若干组 6 个数的号码组,然后要求你用这4272048 组号码组去与他设定的“若干组 6 个数的号码组”比较,如果4272048 组中的之一与其他设定的“若干组 6 个数的号码组”每一组都无三个以上重复数字,则这一组号码为符合条件的号码组 而这个“同一组号码不得出现4连号及4连号以上的连号”是我出主意,目的是想把4272048 组(33选7的号码组合全集)数量降下来,因为4连号及4连号以上的连号这样的号码组中奖几率太小了。所以可以先行从4272048 组(33选7的号码组合全集)移去,不用参与与他设定的“若干组 6 个数的号码组”比较。 这样说,你该清楚了吧?

九洲方除百尺冰,映秀又遭蛮牛耕。汽笛嘶鸣国旗半,哀伤尽处是重生。     -老K
治国就是治吏。礼义廉耻,国之四维。四维不张,国之不国。   -毛泽东
2005-09-14 20:49
jys07
Rank: 1
等 级:新手上路
帖 子:98
专家分:0
注 册:2005-9-9
收藏
得分:0 
首先十分感谢kai的热心帮助,也谢谢knocker的支持,我想可能是我没说明白的缘故吧,我不明白上面所说的测试数字,象knocker所说的33选7有4272048组,这个是对的,10选7有120种组合
2005-09-14 21:14
Knocker
Rank: 8Rank: 8
等 级:贵宾
威 望:47
帖 子:10454
专家分:603
注 册:2004-6-1
收藏
得分:0 
jys07,你的想法是错误或者说是无法办到的。我解释给你听: 1。33选7有4272048组,假如你设定50组6个号码的数组,那么,就要计算机比较 4272048 X 50 次 假定,计算机1秒能比较 1000 次(注意,这是个假定,这个“比较一次”是一次比较复杂运算过程,不是通常你听的计算每秒运计算几亿次这个概念),那么你算算全部比下来要多少时间? 2。经比较后的得到的号码组还是非常非常庞大的,这个我刚才写了个程序验证了一下,已经可确定了。 3。我写的程序这里 [attach]3096[/attach]

九洲方除百尺冰,映秀又遭蛮牛耕。汽笛嘶鸣国旗半,哀伤尽处是重生。     -老K
治国就是治吏。礼义廉耻,国之四维。四维不张,国之不国。   -毛泽东
2005-09-14 21:29
Knocker
Rank: 8Rank: 8
等 级:贵宾
威 望:47
帖 子:10454
专家分:603
注 册:2004-6-1
收藏
得分:0 
过滤数据 ==》可以自动随机生成,也可以你输入,数与数之间有空格就行了,一组一行

只是写来做测试的,所以容错方面没怎么做。生成的结果与自动生成的过滤数据有可能会有重复,因为都是采用随机数生成的,但是在程序设定的范围几率是很小的。

九洲方除百尺冰,映秀又遭蛮牛耕。汽笛嘶鸣国旗半,哀伤尽处是重生。     -老K
治国就是治吏。礼义廉耻,国之四维。四维不张,国之不国。   -毛泽东
2005-09-14 21:44
快速回复:33 选 7
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.020306 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved