求组合数、排列数等

最近写程序一直遇到组合数,排列数等问题。文章介绍程序实现全排列$A_{n}^{n}$、组合$C_{n}^{k}$ 中每个项的列举。

全排列$A_{n}^{n}$ 有顺序的排列n 个数;

组合$C_{n}^{k}$ 从n 个数中选取k 个进行无顺序的组合;

附:一般性的排列$A_{n}^{k}$ 可以通过组合和全排列一起完成。

继续阅读

重载类型转换符

C++ 程序员都知道重载运算符:

   1: operator++

   2: operator==

   3: operator>>

比如C++ 中的输入输出:

   1: cout<<"Hello World!"<<endl;

   2: cin>>&value>>endl;

 

实际上就是重载了”>>” 和”<<”  运算法,但如果说重载类型转换符,可能不是所有的程序员都用到过,最近写一个配置文件的类就碰到了这样的问题。我希望使用 template<class T> T Config::string_to_T(const string& s) 函数返回指定类型的参数,T 类型由调用string_to_T() 的函数确定。比如:

   1: template<class T> T Config::Read(const string& key, const T& value)const{

   2:     ....from key we get value...

   3:     return string_to_T<T>(value);

   4: }

下面是我写的代码:

   1: template<class T> T Config::string_to_T(const string& s){

   2:     T t;

   3:  

   4:     istringstream ist(s);

   5:     ist >> t;

   6:  

   7:     return t;

   8: }

这段代码在大部分时候是没有问题的。

   1: int port

   2: port = Read("port", 0) \\返回了int 类型的端口号

   3: string ip

   4: Read("ip", ip)         \\返回了string 类型的ip 地址

但在T 类型为string 类型的时候,如果s 中包含了空格,那么返回的string 类型只包含了string value 的一部分。比如:

   1: str num_list

   2: port = Read("nums", num_list) \\num 如果对应的值是"1 2 3 4",那么则只返回 1

这是因为ist >> t 格式化输出到T t,当遇到有空格时会将string 分开输出。

解决方法也非常简单,就是的当类型为string 时直接返回,当不是string 类型时,通过上面的string_to_T() 方法即可,这就需要重载类型转换符,代码如下(operator std::string()const  和template<template T> operator T()const 分别重载了string() 和T() 类型转化符):

   1: class ToStringHelper

   2: {

   3:     std::string myValue;

   4: public:

   5:     ToStringHelper( std::string const& value )

   6:         : myValue( value )

   7:     {

   8:     }

   9:     operator std::string() const

  10:     {

  11:         return myValue;

  12:     }

  13:     template <typename T>

  14:     operator T() const

  15:     {

  16:         std::istringstream cvt( myValue );

  17:         T results;

  18:         cvt >> results;

  19:         //  Error checking here...

  20:         return results;

  21:     }

  22: };

  23:  

  24: ToStringHelper

  25: string_to_T( std::string const& s )

  26: {

  27:     return ToStringHelper( s );

  28: }

 

我的提问stackoverflow:http://stackoverflow.com/questions/13658667/how-can-i-return-a-string-as-a-template-class-in-c/

解数独

数独英文为sudoku,是一种在9*9 大小方格内,填充1-9 的游戏,要求每行每列,和9 个3*3 的方格内不允许有重复的数字。前几天写了一个解数独的程序:http://blog.foool.net/sudoku/ ‘set value’将方格中数字顺序填入方格内(0 代表该空格未填数字),‘compute’进行计算,规定时间内完成计算则会返回结果。右边有一个计算范例,测试过独数之道中大师级PK 题,可解。

image         image

继续阅读