对sort的进一步操作

 

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <functional>

using namespace std;

int main()
{
        vector<int> vec;
        vector<int>::iterator p;
        int cc;
        vec.clear();

        while(cin>>cc)
                vec.push_back(cc);

        sort(vec.begin(), vec.end());
        copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, "  "));
        cout<<endl;
        sort(vec.begin(), vec.end(), greater<int>());
        copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, "  "));

        return 0;
}

 

 

泛型算法之stable_sort

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;

const int N = 10;

int main()
{
        int str[8] = {2, 3, 1, 1, 45, 32, 1, 0};
        stable_sort(str, str + 8);
       
        for(int i = 0; i < 8; i++)
                cout<<str[i]<<" ";
        cout<<endl;

        return 0;
}
 

 

 

泛型算法之unique

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;

const int N = 10;

int main()
{
        int str[8] = {0, 1, 1, 2, 3, 2, 1, 1};
        vector<int> vec(str, str + 8);
        vector<int>::iterator p, q;

        p = vec.begin();
        q = unique(vec.begin(), vec.end());

        while(p != q)
                cout<<*p++<<" ";
        cout<<endl;

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

        p = vec.begin();
        q = unique(vec.begin(), vec.end());

        while(p != q)
                cout<<*p++<<" ";
        cout<<endl;

        return 0;
}
     unique()虽然去掉容器中的重复值,但是只去掉相邻的重复值。
    为达到每次只出现单个字母一次的目的,需对其先排序。
    unique()操作容器的长度并没有改变,每个独一无二的元素被放到从头开始的下一个自由槽中。
    实际上结果为01231223,序列1223是算法的废弃部分,unique()返回一个iterator指向废弃部分的开始处,
    典型情况下,这个iterator被传递给相关的容器操作erase()来删除无效元素。

 

 

泛型算法之copy,back_inserter

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;

const int N = 10;

int main()
{
        vector<int> v1, v2;
        vector<int>::iterator p;
        v1.clear(); v2.clear();

        for(int i = 1; i <= 10; i++)
                v1.push_back(i);

        copy(v1.begin(), v1.end(), back_inserter(v2));
        //copy算法把一对iterator当做二个参数,用其标记要拷贝的元素范围,
        //第三个实参是一个iterator,标记要拷贝元素将被放置的起始位置
        //back_inserter被称作iterator适配器;使元素被插入到作为实参的vector的尾部。

        p = v2.begin();

        while(p != v2.end())
                cout<<*p++<<endl;
        return 0;
}

 

 

泛型算法之find

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;

const int N = 10;

int main()
{
        int str[10], cc = 1;
        vector<int> ivec;
        list<int> ilist;
        ivec.clear();
        ilist.clear();

        for(int i = 0; i < N; i++)
        {
                str[i] = cc;
                ivec.push_back(cc + 10);
                ilist.push_back(cc + 20);
                cc++;
        }

        while(cin>>cc)
        {
                if(find(str, str + N, cc) != str + N)
                        cout<<"在数组中找到"<<endl;
               
                if(find(ivec.begin(), ivec.end(), cc) != ivec.end())
                        cout<<"在vector中找到"<<endl;

                if(find(ilist.begin(), ilist.end(), cc) != ilist.end())
                        cout<<"在list中找到"<<endl;
        }

        return 0;
}

 

 

Word之虚拟文本功能

为排版专业工作者准备。

在word中输入: =rand(200,99),再敲回车

=rand(m,n) + 回车, 将产生m段,每段包含n个句子。m <= 200, n <= 99

The quick brown fox jumps over the lazy dog.(这是包含26个字母的最短英文句子)

那只敏捷的棕毛狐狸跃过那只懒狗。

map的三种插入操作

 

#include <iostream>
#include <algorithm>
#include <string>
#include <map>
using namespace std;

int main()
{

        map<string, int> M;
        M.clear();

        /*用下标初始化*/
        M[string("i1")] = 1;
       
        /*用pair初始化*/
        M.insert(pair<string, int>(string("i2"), 2));

        /*直接用内置的value_type初始化*/
        M.insert(map<string, int>::value_type ("i3", 3));

        map<string, int>::iterator p = M.begin();
        while(p != M.end())
        {
                cout<<"first: "<<p->first<<" secnd: "<<p->second<<endl;
                p++;
        }
        return 0;
}

 

 

对容器的一些操作

 

        vector附初值vector<int> ivec(vec_size, 100);
        list   附初值list<int> ilist(list_size, 11);
        list类型的重新设置容器长度 ilist.resize(2 * ilist.size());
    容器类型是支持一组关系操作符的,可以用来比较二个容器大小(<,>,=)。不过,对于能够定义的容器的类型有三个限制
    <1>.元素类型必须支持等于操作符
    <2>.元素类型必须支持小于操作符
    <3>.元素类型必须支持一个缺省值。
    迭代器(iterator)提供一种一般化的方法,对顺序或关联容器类型中的每个元素进行连续访问。
    通过数组实现vector的初始化:
    int cc[4] = {1, 2, 3, 4};
    vector<int> ivec(cc, cc + 4);第二个指针指向的对象不包含在要被拷贝或遍历的元素之中。
 
    任意位置插入元素:
ivec.insert(ivec.begin(), 100);
    更加随机化的插法: 
q = find(ivec.begin(), ivec.end(), 5);
ivec.insert(q, 99);
第一个参数是一个位置,第二个参数是将要被插入的值,这个值将被插入到有iterator指向的位置的前面。
在某个位置插入指定数量的元素:
    ivec.insert(ivec.begin(), 10, -1);在begin()位置插入10个-1
向容器插入一段范围内的元素:
    ivec.insert(ivec.begin(),cc, cc + 4);
    泛型算法:把所有容器类型的公共操作抽取出来,形成一个通用算法集合,它能够被应用到全部容器类型以及内置数组类型上。

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高。

八皇后问题(递归+非递归)

一.问题描述

在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;
}