vector PK list

 

        vector表示一段连续的内存区域，每个元素被顺序存储在这段内存中。对vector的随机访问效率很高，因为每次访问离vector起始处的位移都是固定的。但是，在任意位置，而不是vector的末尾插入/删除元素，其效率很低，需要把待插入/删除元素的右边的每个元素的复制一遍。
       list表示非连续的内存区域，并通过一对指向首尾元素的指针双向链接起来，从而是允许向前和向后二个方向进行遍历的。在list的任意位置插入和删除元素的效率很高：指针必须被重新赋值，但不需拷贝元素来实现移动。另一方面，它对于随机访问效率不高：访问一个元素需要遍历中间元素。
        选择顺序容器类型的一些准则：
<1>.如果我们需要随机访问一个容器，则vector要比list好的多。
<2>.如果我们已知要存储元素的个数，则vector比list要好。
<3>.如果我们需要的不只是二端插入和删除元素，则list好。
<4>.除非我们需要在容器首部插入和删除元素，否则vector比deque好。
       一个需要动态增长的vector必须分配一定的内存以便保存新的序列，按顺序拷贝旧序列的元素以及释放旧的内存。为提高效率，实际上vector并不是随每个元素的插入而增长自己，而是当vector需要增长自身时，它实际分配的空间比当前所需的空间要多一些。故而对于小的对象，vector在实践中的效率比list高。

以前博文 Comments(1) Jun 11, 2009 06:34:23 AM

八皇后问题（递归+非递归）

一．问题描述

在8×8格的国际象棋棋盘上放置八个皇后，使得任意两个皇后不能互相攻击，即任何行、列或对角线（与水平轴夹角为45°或135°的斜线）上不得有两个或两个以上的皇后。这样的一个格局称为问题的一个解。请用递归与非递归两种方法写出求出八皇后问题的算法。

二．解题思路描述

一个正确的解应当是每一列，每一行，每一条斜线上均只有一个皇后。

对于递归算法，本人才有模拟的方式进行，而且，我觉得开辟一个二维数组更显而易见。首先，从空棋盘开始摆放，保证第m行m个皇后互不攻击，然后摆放第m+1个皇后。当然对于第m+1个皇后可能有多种摆放方法，由此，我必须一一枚举，采用回溯策略是可行且合乎逻辑的。 

而对于非递归算法，我只是借助于书本上一个递归改为非递归的框架，依次搭建而已。

在此过程中，我采用一维数组，一位对于八皇后问题，每一行不可能存在二个及二个以上的皇后，board[i]表示第i行棋盘摆放的位置为第board[i]列。递归方法借助于系统提供的栈，而我非递归算法的实现，仅仅是自己构造一个栈而已。

递归解法

 

#include <iostream>
#include <cstdio>
#include <sys/timeb.h>
using namespace std;

const int MAX_SIZE = 100;
enum flag {blank ='X',queen = 1};

char Chess[MAX_SIZE][MAX_SIZE];//棋盘图
int n;//解决n皇后问题
int total;//用于计摆放方式


void Init()
{//对棋牌进行初始化
        for(int i = 0; i < n; i++)
                for(int j = 0; j < n; j++)
                        Chess[i][j] = blank;
        total = 0;//初始时有零中摆放方式
}

bool Judge(int r,int c)
{//判断(r,c)位置是否可放置
        int i,j;
        for(i = r + 1; i < n; i++)
                if(Chess[i][c] == queen)
                        return false;//说明c列上已有一皇后
        for(i = c + 1; i < n; i++)
                if(Chess[r][i] == queen)
                        return false;//说明r行上已有一皇后
        for(i = r + 1, j = c + 1; (i < n) && (j < n); i++, j++)
                if(Chess[i][j] == queen)
                        return false;//45度斜线上已有一皇后
        for(i = r + 1, j = c - 1; (i <n) && (j >= 0); i++, j--)
                if(Chess[i][j] == queen)
                        return false;//135度斜线上已有一皇后
        return true;//排除四种情况后，说明(r,c)点可放置皇后
}

void Backtrack(int k,int cnt)
{//回溯算法主程序
       
        if(k < 0 || cnt == n)//棋牌摆放完毕 or 以摆满n后
        {
                if(cnt == n)
                {
                        printf("No.%d:\n",++total);
                        for(int i = 0; i < n; i++)
                        {
                                for(int j = 0; j < n; j++)
                                        printf(" %c ",Chess[i][j]);
                                putchar('\n');
                        }                     
                        putchar('\n');
                }
        }
        else
        {
                int r = k / n, c = k % n;
                if(Judge(r,c))
                {//可放置一皇后
                        Chess[r][c] = queen;
                        Backtrack(k-1,cnt+1);
                        Chess[r][c] = blank;
                }
                Backtrack(k-1,cnt);
        }
       
}

int main()
{//此为主函数
        timeb t1,t2;
        long kk;
        cout<<"输入皇后个数:";
        while(cin>>n)
        {
                        Init();
                        ftime(&t1);
                        Backtrack(n*n-1,0);
                        ftime(&t2);
                        cout<<"计算"<<n<<"后问题总共可有"<<total<<"种摆法!"<<endl;
                        kk = (t2.time-t1.time)*1000 + t2.millitm-t1.millitm;
                        cout<<"本次回溯耗时:"<<kk<<"毫秒"<<endl;
                        system("PAUSE");
                        cout<<"输入皇后个数:";
        }
        return 0;
}
 

非递归解法

 

#include <iostream>
#include <sys/timeb.h>
#define N 100
using namespace std;

int board[N];
int n,sum;

void init()
{
        for(int i = 1; i <= n; i++)
                board[i] = 0;
}

void display()
{
        int i,j;
        cout<<"No."<<sum<<endl;
        for(i = 1; i <= n; i++)
        {
                for(j = 1; j <= n; j++)
                        if(board[i] == j)
                                cout<<"Q ";
                        else
                                cout<<"X ";
                cout<<endl;
        }
        cout<<endl;
}

bool canPut(int k)
{
        for(int i = 1; i < k; i++)
                if((abs(k - i) == abs(board[k] - board[i])) || board[i] == board[k])
                        return false;//1.是否在同一斜线;2.是否位于同一列
        return true;
}

void Backtrack()
{
        board[1] = 0;
        int k = 1;
        while(k > 0)
        {
                board[k]++;
                while((board[k] <= n) && !(canPut(k)))
                        board[k] += 1;
                if(board[k] <= n)
                        if(k == n)
                        {
                                sum++;
                                display();
                        }
                        else
                        {
                                k++;
                                board[k] = 0;
                        }
                else
                        k--;

        }
}

int main()
{
        timeb t1,t2;
        long kk;
        cout<<"输入皇后个数:";
        while(cin>>n)
        {
                init();
                sum = 0;
                ftime(&t1);
                Backtrack();
                ftime(&t2);
                cout<<"总共排列方式为:"<<sum<<endl;
                kk = (t2.time-t1.time)*1000 + t2.millitm-t1.millitm;
                cout<<"本次回溯耗时:"<<kk<<"毫秒"<<endl;
                system("PAUSE");
                cout<<"输入皇后个数:";
        }
        return 0;
}

 

 

 

 

以前博文 Comments(1) Jun 04, 2009 10:15:47 AM

bitset的一些操作总结

 

/******************************************************************
** 文件名:bitset.cpp
** Copyright (c) 2009 *********
** 创建人: Xredman
** 日期: 6.2
** 修改人:
** 日期:
** 描述: 本程序实现对bitset的一些操作，主要用于熟悉位操作
**
** 版本:
**--------------------------------------------------------------------------
---
******************************************************************/

#include <iostream>
#include <bitset>
#include <string>
using namespace std;

int main()
{
        /*-----声明-----*/

        bitset<32> bt1;
        /*位的计数从0开始,即0~31
          缺省情况下，所有的位都被初始化为0
        */

        bitset<32> bit2(0xffff);//位构造函数显式提供一个无符号参数

        string bitval("1010");
        bitset<32> bit3(bitval);

        if(bt1.any())//当bitset对象含有一位或多位被置为1时，返回true
                cout<<"初始化是含有1."<<endl;
        else if(bt1.none())//当bitset对象不含有1时，返回true
                cout<<"初始化是不含1."<<endl;

        /*--------置位操作----------*/

        bt1[26] = 1;//将26位设置为1
        bt1.set(27);//将27位设置为1

        bt1[26] = 0;//将26位设置为0
        bt1.reset(26);//将26位设置为0

        /*全部置位
        bt1.set();
        bt1.reset();*/

        cout<<"被置为1的位数有:"<<bt1.count()<<endl;
        //返回被置为1的的位的个数

        if(bt1.test(27))//或者用下标操作符bt1[27]
                cout<<"第27位被置为1."<<endl;

        /*-----翻转操作-----*/

        bt1.flip(0);//翻转第0位
        bt1[1].flip();//翻转第1位
        bt1.flip();//全部翻转

        /*-----类型转化-----*/

        string sbt = bt1.to_string();
        unsigned long lbt = bt1.to_ulong();
       

        return 0;
}
 

以前博文 Comments(2) Jun 02, 2009 08:53:42 AM