The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

#

优先队列priority_queue 实现哈弗曼树WPL的计算

#include<iostream>
#include
<queue>
#include
<functional>
using namespace std;

priority_queue
<int,vector<int>,greater<int>>myqueue;

int main ()
{

    
int n;
    
int i;
    
int sum=0;
    scanf(
"%d",&n);
    
for(i=1;i<=n;i++)
    
{
        
int temp;
        cin
>>temp;
        myqueue.push(temp);
    }

    
while(myqueue.size()!=1)
    
{
        
int temp;
        temp
=myqueue.top();
        sum
+=temp;
        myqueue.pop();
        temp
=myqueue.top();
        sum
+=temp;
        myqueue.pop();
        myqueue.push(sum);
        sum
=0;
    }

    cout
<<myqueue.top()<<endl;
    system(
"pause");
    
return 0;
}

posted @ 2009-03-28 23:24 abilitytao 阅读(363) | 评论 (0)编辑 收藏

POJ 1700-过河问题 经典智力题

题目描述:在漆黑的夜里,四位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话,大家是无论如何也不敢过桥去的。不幸的是,四个人一共只带了一只手电筒,而桥窄得只够让两个人同时过。如果各自单独过桥的话,四人所需要的时间分别是1、2、5、8分钟;而如果两人同时过桥,所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是,如何设计一个方案,让这四人尽快过桥。

解题思路:
当人数等于1,2,3的时候:答案很容易得出;
当人数大于等于4时:

若设过桥速度最快的那个人过桥时间为a,第二快为b;过桥第二慢的那个人过桥时间为y,最慢为z;
此时有两种过桥方案:
一.最快和次快的人先过,然后最快的回来,然后最慢与次慢的人再过,次快的回来;
二.最快的和最慢的过,快的回来,在和次慢的过,快的再回来;

第一种方法时间为b*2+a+z
第二种方法时间为y+z+2*a
如果第一种大于第二种 有2*b+a+z>y+z+2*a
化简得
2*b>y+a;
此时只要比较2*b和a+y的大小即可知道那种方法更优 O(∩_∩)O~ 编程解决即可
#include<iostream>
#include
<algorithm>
#include
<numeric>
using namespace std;


int a[1000];

int main()
{
    
int testcase;
    
int n;
    
int i;
    
int j;
    
int sum=0;
    scanf(
"%d",&testcase);
    
for(j=1;j<=testcase;j++)
    
{
        sum
=0;
        scanf(
"%d",&n);
        
for(i=1;i<=n;i++)
            scanf(
"%d",&a[i]);
        sort(a
+1,a+1+n);
        
while(n)
        
{
            
            
if(n==1)
            
{
                sum
+=a[1];
                n
=0;
            }

            
else if(n==2)
            
{
                sum
+=a[2];
                n
=0;
            }

            
else if(n==3)
            
{
                
                sum
+=(a[2]+a[3]+a[1]);
                n
=0;
            }

            
else if(n>=4)
            
{
                
                
                
if(2*a[2]>a[1]+a[n-1])
                
{
                    sum
+=(a[n-1]+a[n])+2*a[1];
                    n
-=2;
                }

                
                
else
                
{
                    sum
+=(a[2]+a[1]+a[n]+a[2]);
                    n
-=2;
                }

            }

            
            
        }

        printf(
"%d\n",sum);
    }

    system(
"pause");
    
return 0;
    
}




说句题外话,据说去年南大保研的面试题就是这道题,一模一样,呵呵 只可惜我还没到保研的时间。。。

posted @ 2009-03-28 22:58 abilitytao 阅读(2894) | 评论 (10)编辑 收藏

POJ 2083-Fractal

此题与上一题类似,一次AC;
由于控制台屏幕太小 这次我将结果保存在文件中;
#include<iostream>
#include
<cmath>
#include
<algorithm>
#include
<cstdlib>
#include
<cstdio>
#include
<fstream>
using namespace std;

char mymap[2500][2500];

int leftdot;
int rightdot;
int topdot;
int bottomdot;


void figure(int x,int y,int degree)
{
    leftdot
=min(leftdot,y);
    rightdot
=max(rightdot,y);
    topdot
=min(topdot,x);
    bottomdot
=max(bottomdot,x);


    
if(degree==1)
    
{
        mymap[x][y]
='X';
    }

    
else
    
{

        
int dis=(int)pow((double)3,degree-2)*2;
        figure(x,y,degree
-1);
        figure(x,y
+dis,degree-1);
        figure(x
+dis,y,degree-1);
        figure(x
+dis/2,y+dis/2,degree-1);
        figure(x
+dis,y+dis,degree-1);
    }




}



int main()
{

    
int n;
    
int i,j;
    ofstream file;
    file.open(
"test.txt");
    
while(scanf("%d",&n))
    
{
        rightdot
=-100000000;
        leftdot
=100000000;
        topdot
=1000000000;
        bottomdot
=-1000000000;
        memset(mymap,
' ',sizeof(mymap));
        
if(n==-1)
            
break;
        figure(
1,1,n);
        
for(i=leftdot;i<=rightdot;i++)
        
{

            
for(j=topdot;j<=bottomdot;j++)
                file
<<mymap[i][j];
            file
<<endl;
        }

        file
<<'-'<<endl;
    }

    file.close();
    
return 0;
}


答案请见:/Files/abilitytao/test.txt

posted @ 2009-03-27 23:44 abilitytao 阅读(517) | 评论 (0)编辑 收藏

POJ 1941-The Sierpinski Fractal 感悟递归之美^_^

原题链接:http://162.105.81.212/JudgeOnline/problem?id=1941

解题方法:刚开始拿到这道题,我的第一反应是要一行一行的输出,不过做了几分钟之后发现:在题述意思下行与行之间似乎没有规律可言;
所以这种方法只能作罢;后来看了看discuss,有人提到用递归的方法来做这道题,这才恍然大悟:像种大问题嵌套类似之子问题的时候,递归不是最理想的方法么?
开一个很大的二维矩阵(因为不知道N的最大值有多大,矩阵尽量开大一点可以避免越界),然后给出中间某个点的坐标,让它成为整个图形的坐下点坐标,然后递归得“画出”三个子图形(当然还要注意一下递归出口O(∩_∩)O~),即可;当然在不知道这个题目n的最大值时,我们可以每次画图后刷新一边矩阵,不过为了优化速度,我只将n=10的图形画出,然后再由点与点之间的关系,求出各个参数的大小即可;
最后输出,这个没什么可说的了。。。

说句题外话,我交题的时候出现Access denied
幸好过年的时候也遇到过同样情况 用IP地址才可正常访问 大家注意下:

遇到Access denied的用户请通过http://162.105.81.212访问poj



#include<iostream>
#include
<cmath>
#include 
<cstdlib>
using namespace std;
#define MAX 100000000
#define MIN -100000000

char mymap[5000][5000];

int leftdot;
int rightdot;
int topdot;
int bottomdot;

void figure(int x,int y,int deep)
{

    
if(deep==1)
    
{

        mymap[x][y]
='/';
        mymap[x][y
+1]='_';
        mymap[x][y
+2]='_';
        mymap[x][y
+3]='\\';
        mymap[x
-1][y+1]='/';
        mymap[x
-1][y+2]='\\';
    }

    
else
    
{
        
int dis=(int)pow((double)2,deep);
        figure(x,y,deep
-1);
        figure(x,y
+dis,deep-1);
        figure(x
-dis/2,y+dis/2,deep-1);
    }

}



int main ()
{

    
int n;
    
int i,j;
    leftdot
=MAX;
    rightdot
=MIN;
    topdot
=MAX;
    bottomdot
=MIN;
    memset(mymap,
' ',sizeof(mymap));
    figure(
2500,2500,10);
    
    
while(scanf("%d",&n))
    
{

        
if(n==0)
            
break;

        topdot
=2500-(int)pow((double)2,10)+1;
        bottomdot
=topdot+(int)pow((double)2,n)-1;
        leftdot
=2500+(int)pow((double)2,10)-(int)pow((double)2,n);
        rightdot
=leftdot+(int)pow((double)2,n+1)-1;
        
for(i=topdot;i<=bottomdot;i++)
        
{

            
for(j=leftdot;j<=rightdot;j++)
            
{

                printf(
"%c",mymap[i][j]);
            }

            printf(
"\n");
        }

        printf(
"\n");
        
    }

    
return 0;
    system(
"pause");
}


posted @ 2009-03-27 22:08 abilitytao 阅读(2547) | 评论 (0)编辑 收藏

注意一个细节

#include<iostream>
using namespace std;


struct node {
    
int a;
    
char b;
}
;

int main ()
{
    cout
<<sizeof(node)<<endl;
    system(
"pause");
    
return 0;

}

这段代码运行后 您认为应该输出几呢?
上课的时候老师突然提出了这样一个问题,当时我想都没想 直接回答了 5。
呵呵 答案当然是错的 现在来运行一下这个程序 发现这个程序的结果是8;

 
PS:感谢楼下两位朋友的提问 让问题变得更有意思了 内部原理究竟是怎样的呢?希望知道的朋友能够予以解答
我在这里仅给出一些测试现象 
 struct node
{
};
输出为1

struct node
{
char a;
};
输出为1

struct node
{
int a;
double b;
};
输出为16

struct node
{
char a;
char b;
char c;
char d;
char e;
}
输出为5

posted @ 2009-03-26 00:10 abilitytao 阅读(264) | 评论 (7)编辑 收藏

POJ 2503 -Babelfish 再谈字典查询问题

记得第一次做这个题目的时候 用了很复杂的c语言算法 代码冗长 现在用类来做 代码非常简洁
这个方法只有一个缺点 就是耗时比C风格的代码大很多 所以建议参加ACM的同学还是尽量用C写吧

#include<iostream>
#include
<string>
#include
<map>
#include
<sstream>
using namespace std;
map
<string,string>mymap;

int main()
{
    
string line;
    
string a;
    
string b;
    
while(getline(cin,line))
    
{
        
if(line.length()==0)
            
break;
        istringstream test(line);
        test
>>a>>b;
        mymap[b]
=a;
    }

    
while(cin>>a)
    
{
        
if(mymap[a].length()!=0)
            cout
<<mymap[a]<<endl;
        
else
            cout
<<"eh"<<endl;
    }

    
return 0;
}




posted @ 2009-03-24 22:53 abilitytao 阅读(488) | 评论 (0)编辑 收藏

C++ 中库函数bsearch的简单研究(含示例)

/*bsearch函数声明如下:

void *bsearch(const void *key, const void *base, size_t *nelem, 
              size_t width, int(*fcmp)(const void *, const *)); 

参数的意思和qsort的差不多,区别在于:
1. qsort用来排序,bsearch用二分法来查找元素
2. bsearch中的base必须是升序排列的数组!!!
3. 如果数组里有重复的答案,则bsearch会返回其中一个的地址 (具体返回哪一个不确定)
4. bsearch有五个自变量,第一个是要找的东西,剩下的跟qsort一模一样
5. bsearch如果没找到所求则回传NULL ,否则回传该元素被找到的地址(void *) 
*/




#include
<iostream>
#include
<cstdlib>
using namespace std;


int compare(const void*a,const void *b)
{
    
return *((int*)a)-*((int*)b);
}



int main()

{
    
int a[100];
    
int i;
    
for(i=0;i<100;i++)
        a[i]
=i+1;
    i
=50;
    
int *result;
    result
=(int*)bsearch((void*)&i,(void*)a,100,sizeof(a[0]),compare);
    cout
<<i<<' '<<*result<<endl;
    system(
"pause");
    
return 0;
}



值得特别注意的是:函数的第一个元素是一个地址变量,而不是一个int型或者是float型的变量。

posted @ 2009-03-24 11:27 abilitytao 阅读(742) | 评论 (1)编辑 收藏

C++标准库简介(转)

C++标准库的所有头文件都没有扩展名。C++标准库的内容总共在50个标准头文件中定义,其中18个提供了C库的功能。 <cname>形式的标准头文件【 <complex>例外】其内容与ISO标准C包含的name.h头文件相同,但容纳了C++扩展的功能。在 <cname>形式标准的头文件中,与宏相关的名称在全局作用域中定义,其他名称在std命名空间中声明。在C++中还可以使用name.h形式的标准C库头文件名。

C++标准库的内容分为10类:

C1.语言支持 C2.输入/输出 C3.诊断 C4.一般工具 C5.字符串

C6.容器 C7.迭代器支持 C8.算法 C9.数值操作 C10.本地化


C1 标准库中与语言支持功能相关的头文件 头文件  描述 
<cstddef> 定义宏NULL和offsetof,以及其他标准类型size_t和ptrdiff_t。与对应的标准C头文件的区别是,NULL是C++空指针常量的补充定义,宏offsetof接受结构或者联合类型参数,只要他们没有成员指针类型的非静态成员即可。
<limits> 提供与基本数据类型相关的定义。例如,对于每个数值数据类型,它定义了可以表示出来的最大值和最小值以及二进制数字的位数。
<climits> 提供与基本整数数据类型相关的C样式定义。这些信息的C++样式定义在 <limits>中
<cfloat> 提供与基本浮点型数据类型相关的C样式定义。这些信息的C++样式定义在 <limits>中
<cstdlib> 提供支持程序启动和终止的宏和函数。这个头文件还声明了许多其他杂项函数,例如搜索和排序函数,从字符串转换为数值等函数。它与对应的标准C头文件stdlib.h不同,定义了abort(void)。abort()函数还有额外的功能,它不为静态或自动对象调用析构函数,也不调用传给atexit()函数的函数。它还定义了exit()函数的额外功能,可以释放静态对象,以注册的逆序调用用atexit()注册的函数。清除并关闭所有打开的C流,把控制权返回给主机环境。
<new> 支持动态内存分配
<typeinfo> 支持变量在运行期间的类型标识
<exception> 支持异常处理,这是处理程序中可能发生的错误的一种方式
<cstdarg> 支持接受数量可变的参数的函数。即在调用函数时,可以给函数传送数量不等的数据项。它定义了宏va_arg、va_end、va_start以及va_list类型
<csetjmp> 为C样式的非本地跳跃提供函数。这些函数在C++中不常用
<csignal> 为中断处理提供C样式支持

C2 支持流输入/输出的头文件 头文件  描述 
< iostream> 支持标准流cin、cout、cerr和clog的输入和输出,它还支持多字节字符标准流wcin、wcout、wcerr和wclog。
<iomanip> 提供操纵程序,允许改变流的状态,从而改变输出的格式。
<ios> 定义iostream的基类
<istream> 为管理输出流缓存区的输入定义模板类
<ostream> 为管理输出流缓存区的输出定义模板类
<sstream> 支持字符串的流输入输出
<fstream> 支持文件的流输入输出
<iosfwd> 为输入输出对象提供向前的声明
<streambuf> 支持流输入和输出的缓存
<cstdio> 为标准流提供C样式的输入和输出
<cwchar> 支持多字节字符的C样式输入输出

C3 与诊断功能相关的头文件 头文件 描述
<stdexcept> 定义标准异常。异常是处理错误的方式
<cassert> 定义断言宏,用于检查运行期间的情形
<cerrno> 支持C样式的错误信息

C4 定义工具函数的头文件 头文件 描述
<utility> 定义重载的关系运算符,简化关系运算符的写入,它还定义了pair类型,该类型是一种模板类型,可以存储一对值。这些功能在库的其他地方使用
<functional> 定义了许多函数对象类型和支持函数对象的功能,函数对象是支持operator()()函数调用运算符的任意对象
<memory> 给容器、管理内存的函数和auto_ptr模板类定义标准内存分配器
<ctime> 支持系统时钟函数

C5 支持字符串处理的头文件 头文件 描述
<string> 为字符串类型提供支持和定义,包括单字节字符串(由char组成)的string和多字节字符串(由wchar_t组成)
<cctype> 单字节字符类别
<cwctype> 多字节字符类别
<cstring> 为处理非空字节序列和内存块提供函数。这不同于对应的标准C库头文件,几个C样式字符串的一般C库函数被返回值为const和非const的函数对替代了
<cwchar> 为处理、执行I/O和转换多字节字符序列提供函数,这不同于对应的标准C库头文件,几个多字节C样式字符串操作的一般C库函数被返回值为const和非const的函数对替代了。
<cstdlib> 为把单字节字符串转换为数值、在多字节字符和多字节字符串之间转换提供函数

C6 定义容器类的模板的头文件 头文件 描述
<vector> 定义vector序列模板,这是一个大小可以重新设置的数组类型,比普通数组更安全、更灵活
<list> 定义list序列模板,这是一个序列的链表,常常在任意位置插入和删除元素
<deque> 定义deque序列模板,支持在开始和结尾的高效插入和删除操作
<queue> 为队列(先进先出)数据结构定义序列适配器queue和priority_queue
<stack> 为堆栈(后进先出)数据结构定义序列适配器stack
<map> map是一个关联容器类型,允许根据键值是唯一的,且按照升序存储。multimap类似于map,但键不是唯一的。
<set> set是一个关联容器类型,用于以升序方式存储唯一值。multiset类似于set,但是值不必是唯一的。
<bitset> 为固定长度的位序列定义bitset模板,它可以看作固定长度的紧凑型bool数组

C7 支持迭代器的头文件 头文件 描述
<iterator> 给迭代器提供定义和支持

C8 有关算法的头文件 头文件 描述
<algorithm> 提供一组基于算法的函数,包括置换、排序、合并和搜索
<cstdlib> 声明C标准库函数bsearch()和qsort(),进行搜索和排序
<ciso646> 允许在代码中使用and代替&&

C9 有关数值操作的头文件 头文件 描述
<complex> 支持复杂数值的定义和操作
<valarray> 支持数值矢量的操作
<numeric> 在数值序列上定义一组一般数学操作,例如accumulate和inner_product
<cmath> 这是C数学库,其中还附加了重载函数,以支持C++约定
<cstdlib> 提供的函数可以提取整数的绝对值,对整数进行取余数操作

C10 有关本地化的头文件 头文件 描述
<locale> 提供的本地化包括字符类别、排序序列以及货币和日期表示。
<clocale> 对本地化提供C样式支持

 

posted @ 2009-03-24 10:50 abilitytao 阅读(11518) | 评论 (6)编辑 收藏

istringstream类研究

C++程序把输入和输出看作字符流,输入时,程序从输入流中提取字节,输出时,程序把字节插入到输出流中。对于输入输出流既可以来自标准输入输出设备,也可以来自文件,甚至可以来自String对象,三者分别属于iostream family、fstream family、sstream family。
对于iostream类,就是我们通常所说的标准流,它把程序跟标准I/O连接在一起,输入来自键盘,输出送往监视器。
对于fstream类,它把程序跟文件关联起来,输入来自文件,输出到文件。
对于sstream类,它是提供程序和string对象之间的I/O,可通过ostringstream sout和istringstream sin来声明两个对象,分别对应输出流和输入流,这给编程带来极大的方便,例如可以从文本文件中读取一批数字字符到string对象中,再把string对象作为程序的输入流,既可把从文件中读取来的数字字符单个进行读取,从而进行处理。

以上内容为网上转载,呵呵,原来iostream,fstream还有sstream呈三权分立之势。

#include<iostream>
#include
<fstream>
#include
<sstream>

using namespace std;


int main ()
{
    
char str[1000]="12 34.53 【O(∩_∩)O~(*^__^*)】 1234 12.12345678901234567890 #@$#@$#@$&*@#&#(!@#$";    
    istringstream test(str);
    
//test="12 34.53 345342 34.123456789 【O(∩_∩)O~(*^__^*)】"
    int a;
    
double b;
    
char c[100];
    
while(1)
    
{
        test
>>a;
        test
>>b;
        test
>>c;
    }

return 0;
}



以上程序在vc6.0上运行正常;
值得一提的是,经过我的测试,我发现虽然sstream是纯c++的东西,但是它也可以用char型数组进行初始化;
而且输入的数据默认情况下以空格为分隔符;
输入浮点类型的时候,最多只能取到小数点后15位,第15位会进行四舍五入;
如果你的输入格式和数据流格式不匹配,那么将导致程序完全运行错误,不过我很奇怪c++内部为什么不会报错?
只有一种情况例外
对于一个浮点数 比如说123,456
如果先以整数输入,那么得到123
再以浮点数输入,得到0.456;

小结:感觉istringstream和sscanf是同类型的函数,只不过一个属于传统的c语言而另一个属于高级的c++;
用它可以方便的分离字符串,并且可以在字符串长度未知的情况下进行操作,这是sscanf所无可比拟的。

最后,要特别鸣谢的是张宏课上面的那位同学,多谢你的指点 :-)


posted @ 2009-03-23 22:36 abilitytao 阅读(3947) | 评论 (10)编辑 收藏

Eight Queen Problem-浅究八皇后问题

     摘要: 对Rss客户端订阅的朋友表示歉意。  阅读全文

posted @ 2009-03-23 21:58 abilitytao 阅读(1715) | 评论 (1)编辑 收藏

仅列出标题
共42页: First 33 34 35 36 37 38 39 40 41 Last