| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4223 人关注过本帖
标题:33 选 7
取消只看楼主 加入收藏
kai
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:52
帖 子:3450
专家分:59
注 册:2004-4-25
结帖率:100%
收藏
 问题点数:0 回复次数:11 
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
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
kai
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:52
帖 子:3450
专家分:59
注 册:2004-4-25
收藏
得分:0 
好的, 别的就不多说了, 看来沟通确实有点问题.
能面对面的说,就好了, 再说不清楚就举个例子,等等. 比现在这样好多了.

你上面的程序,我也不想看, 这样不客观, 不全面, 得出的数据没啥意思, 我还是要全部解.

这样吧, 我们把问题简单化, 把范围缩小些. 我们先来说 7 出 4.
你们来告诉我所有解. 我来看看到底所有解是什么?
如果不便写在帖子里, 那就写成 txt 文件发到我的Email.
我的Email地址:   kaihua1@

自由,民主,平等,博爱,进步.
中华民国,我的祖国,中华民国万岁!中华民国加油!
本人自愿加入中国国民党,为人的自由性,独立性和平等性而奋斗!
2005-09-14 23:32
kai
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:52
帖 子:3450
专家分:59
注 册:2004-4-25
收藏
得分:0 
jys07, 你14楼的我看到了, 我的程序中改动了一个地方就和你的一样了. 可是你13 说的是21选5, 可是给出的却是6个数, 这是怎么回事?

自由,民主,平等,博爱,进步.
中华民国,我的祖国,中华民国万岁!中华民国加油!
本人自愿加入中国国民党,为人的自由性,独立性和平等性而奋斗!
2005-09-15 00:21
kai
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:52
帖 子:3450
专家分:59
注 册:2004-4-25
收藏
得分:0 
我是彻底糊涂了, 你21选5怎么出来个6个数, 这不是就变成21选6了吗?
你们把算法写出来算了, 我按你们的算法来写程序. 至于结果对不对,就取决于你们的算法了.

自由,民主,平等,博爱,进步.
中华民国,我的祖国,中华民国万岁!中华民国加油!
本人自愿加入中国国民党,为人的自由性,独立性和平等性而奋斗!
2005-09-15 01:49
kai
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:52
帖 子:3450
专家分:59
注 册:2004-4-25
收藏
得分:0 
一会儿5个数,一会儿6个数,条件怎么可以变来变去呢?我都被你搞糊涂了,说实在的,你越说,我越不理解了。
我们好像是两个星球上的人,彼此怎么说都不能明白对方的意思。看来你要中个奖还真不容易。

那个knocker又自说自话,搞什么筛选,他好像是明白了你的意思,我也不清楚,他到底是真的明白了你的意思,还是也歪曲了你的意思。咳。。。你又缺乏表达能力。。。真是拿你没办法,要不然程序早就运行出了结果。

怎么办呢?你如果知道个算法,哪怕很笨的算法,那我也知道,这些数组产生的过程,那我可以在你的算法的基础上优化。而你说描述的那些条件啊什么的,我看了半天也不能理解你的意思,看来是在对牛弹琴啊。

你先和knocker 说说,在你明确他的算法真确的基础上,让他来和我说。

自由,民主,平等,博爱,进步.
中华民国,我的祖国,中华民国万岁!中华民国加油!
本人自愿加入中国国民党,为人的自由性,独立性和平等性而奋斗!
2005-09-15 07:01
kai
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:52
帖 子:3450
专家分:59
注 册:2004-4-25
收藏
得分:0 
knocker, 可以做,用处理图像的方式来处理。33个数用33个Bit 来表示,但是计算机开辟空间是以Byte 为单位的,所以就只能用40个Bit来表示33个数,当然有7个Bit是闲着不用的。那就是说每个组合需要5个Byte。那么4272048 就意味着 4272048 * 5 = 21360240 Byte = 20859,61KB = 20,37MB 对于一个图像来讲这样的大小是可以处理的。 如果这样来做的话,就要用到WinApi了。通过这样的处理就产生了你所说的那个原始数据库了。 从数据库中读数据,就是将这个图像文件5个Byte作为一个Block读出来,然后从中提取33个Bit,并得出那组数字。 这样提取出来的数字再与你所说的那个过滤数组比较。 至于比较的依据是什么,也就是说以什么为评判标准,来确认"符合" 或者 "不符合", 这一点,我还是不太清楚。

自由,民主,平等,博爱,进步.
中华民国,我的祖国,中华民国万岁!中华民国加油!
本人自愿加入中国国民党,为人的自由性,独立性和平等性而奋斗!
2005-09-15 19:38
kai
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:52
帖 子:3450
专家分:59
注 册:2004-4-25
收藏
得分:0 
我现在看来是外星人了,和地球人沟通还真不容易。

自由,民主,平等,博爱,进步.
中华民国,我的祖国,中华民国万岁!中华民国加油!
本人自愿加入中国国民党,为人的自由性,独立性和平等性而奋斗!
2005-09-16 23:18
kai
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:52
帖 子:3450
专家分:59
注 册:2004-4-25
收藏
得分:0 
中不中奖完全是天数,没有程序可以帮你的。
我到有个想法,对于开奖,我觉得,我有个理论,不知大家是否同意。将每一次开奖的号码统计出来,也就是说建立一个已开奖号码数据库。然后建议一个所有组合的数据库, 从所有组合的数据库中将已开奖号码除去,并除去连续排列的数组,如1 2 3 4 5 6 7,还有2 3 4 5 6 78,这些连续数出现的可能几乎没有。

如果你认同的话,我可以根据上面的算法帮你写个程序。但是考虑到即便这样,产生的数组还是很大的。然后再用随机的方法帮你产生你所要的数组,比如你想产生100组,就输入100, 然后就会产生100组 7 位排列的数字。

你要搞的那个摇奖的程序,我以前也写过,不过不是你的这种,只是随机的产生几组数而已。靠这个从未拿过什么奖。

自由,民主,平等,博爱,进步.
中华民国,我的祖国,中华民国万岁!中华民国加油!
本人自愿加入中国国民党,为人的自由性,独立性和平等性而奋斗!
2005-09-17 05:27
快速回复:33 选 7
数据加载中...
 
   



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

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