月度归档:2018年09月

线段树

        线段树是一种适合进行区间运算的数据结构,一般为完全二叉树形状。树上的每个节点,都有着自己维护的数据区间,节点中保存了自己所维护的区间中的有用的数据,相邻区间可进行区间加法的逻辑运算。树叶是点信息,包含了原始数据,只负责维护自己,其他节点负责维护自己的子树,根节点维护整个区间。这种分区间而维护计算的方法实际上是分治思想。使用完全二叉树维护可以使查询/更新达到

O(lgN) 的复杂度。

        因为室友睡了,不能打字影响,所以明天再更新       

心累

最近牵扯了太多利益相关问题,这种问题往往很烦人。

然而我又不得不扯进去,实在是,坑爹哇!

其实想一想,大概有两个原因:

1.实力不够,如果已经强到可以无视某些东西的地步,就不需要牵扯这些事情了

2.心性有缺,内心不平静,才会让这些事情一直纠结在心上。

总的来说就是这样,哎。

 

 

回溯法与八皇后问题

        昨天晚上写了一个OJ上的八皇后问题,然后居然TLE了。。。。(本人弱鸡)。。。然后就躺在床上想怎么优化,想着想着就睡着了,做了一个令人感到忧伤的梦,然后醒了,然后就想到了怎么优化了。。。。当然我很菜。。。用的还是简单回溯的算法,其实就是DFS,皇后多了还是很耗时的,所以,各位皇帝麻烦您们专一一点好吧。

        好吧,先说回溯法吧,回溯法和DFS差不多,其思想就是:“我就是要一条路走到黑,走到黑了然后感觉不对,就赶紧返回上一层,看看有没有其他的路,如果没有走到黑,反而走到白了,那就恭喜我,我成功搞出一条通天大道,那么,我。。我。。我我我还是要返回上一层。。。。看看有没有其他的路。。。“讲道理一条路就中了,但可恶的出题人太贪心,总喜欢让我们把所有的路都找到,这不是坑爹呢吗。。。。

大致的框架可以写为:

void func(int step){

    1判断路是不是死路,如果是就返回;

    2如果判断是不是已经走出一条通天大道了,如果已经是了,那就在这里搞一些操纵,然后。。。还是要返回上一层。。。

   for chioce in allOption{

       标记一下这个chioce被选过了(某些情况下需要)

        func(step+1);//走下一步        

     }

}

注意,一定不要把1嵌入2里面,如果这样做的话,会DFS出所有选择的全排列,然后再判断是否可行,这样就没有剪枝的效果了。

 

 

好吧我知道本人讲的很渣渣,很坑爹,应该没有人能看懂。。。。嗯。。。如果能画图就好了。。。。但是我很懒。。不想画完图用手机拍照然后再传到电脑上然后在传到博客上。。。。。。。


题目:

检查一个如下的6 x 6的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

上面的布局可以用序列2 4 6 1 3 5来描述,第i个数字表示在第i行的相应位置有一个棋子,如下:

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。

解法(代码里面的注释应该很清楚):

#include <iostream>
using namespace std;
void queen(int step);
int n;//有多少个皇后
int count;//记录成功的方案
int book[14];//标记
int a[14];//a[1]表示第一行的皇后在第几列,a[2]表示第二行的。。。。。
int main(){
    cin>>n;
    queen(n);
    cout<<count;
    return 0;
}
void queen(int step){
    int LastLine=n-step;//上一步摆下来的皇后,因为摆放皇后时候已经用了book数组进行标记约束,所以不需要判断行列
    for(int i=1;i<LastLine;i++){//判断是否在同同一斜线上
        if(a[LastLine]-a[i]==LastLine-i||a[LastLine]-a[i]==i-LastLine){
            return;
        }
    }
    /*for(int i=1;i<=n-step;i++){//这里是原来的判断是否在同一条斜线上的算法,但是算法复杂度很高,分析原因发现
        for(int j=i+1;j<=n-step;j++){//这个算法是,对于每一行,都有对比其他的行,重复了很多
            if(a[j]-a[i]==j-i||a[j]-a[i]==i-j){//仔细思考发现,只需要判断新加入的皇后符不符合要求就行,所以
                return;//换成了上面的算法,复杂度是o(N)
            }
        }
    }*/
    if(step==0){//拜访了最后一个皇后,已经得出了一种解法
        count++;
        if(count<=3){
            for(int i=1;i<=n;i++){
                cout<<a[i]<<' ';
            }
            cout<<endl;
        }
    }else{
        //进行本次放置,然后递归下一次
        for(int i=1;i<=n;i++){//每次摆放这一行的皇后的时候,都有N列可以摆,意思就是有N个岔路口。
                              //我们选一个深入,等这个返回之后,再选下一个进行深入,所以是一个for循环
            if(!book[i]){//如果第i列还没有黄后占场子
                book[i]=1;//标记一下我要占上
                a[n+1-step]=i;//摆放皇后
                queen(step-1);//深入下一个路口
                book[i]=0;//返回了,就要开始走下一个差路口(下一列),所以这一列的标记取消掉
            }
        }
    }
}

 

记录一个C/C++使用使用sqlite3的小坑

运行查询指令的时候,无法查询到信息,是不会进入回调函数的,可以利用这个点判断数据库里面是否有查询的记录。

 

技术细节稍后更新

—————————-2018.9.8更新————————————

        首先回调函数一般是指,自己定义一个函数的功能,然后把函数作为参数传入另一个函数里面,在另一个函数里面会执行我们自己定义的函数,这个我们定义的函数叫回调函数。回调函数的参数需要符合另一个函数的要求,才能被传入、调用。而这另一个函数一般是我们无法直接更改内容的一个黑盒,但是我们可以通过自己定义的回调函数来操控程序。

        c/c++的sqlite库中执行SQL命令的函数sqlite3_exec原型如下:

sqlite3_exec(sqlite3* pdb, const char *sql, sqlite_callback func, void *data, char **errmsg);

sqlite3* pdb是指向已经打开的数据库的指针;

const char * sql是需要执行的sql语句,注意在c++中如果是string的话需要传参的时候用c_str()更改一下类型;

sqlite_callback func是一个回调函数,如果不需要回调,可以传实参为NULL,使用select语句时,每产生一条记录都会调用一次回调函数;

void *data将会作为参数传入回调函数,作为回调函数的第一个参数,利用这点可以向回调函数中动态传入数据;

char errmsg保存执行命令时发生的错误,注意errmsg是char类型的,但是错误语句应该是char类型的,那么我们传入实参的时候就一个调用&取一个char类型的变量,这样就好了,sqlite3_exec执行完毕之后错误会保存在这个变量指向的字符串里面;


回调函数:

typedef int(*sqlite3_callback)(void*,int,char**,char**);

void*是exec里面的第四个参数,int是记录的列数,第一个char是一个二维数组,记录查到的值,第二个char保存键名


 

         当使用sqlite3_exe执行select语句时,如果没有查询到记录,是不会报错的,那么怎么知道没有查到记录呢?

如果查到了相关记录,会调用回调函数,查询到的记录条数是0的话,就不会调用,可以利用sqlite3_exec的第四个void *参数,向回调函数里面传入一个变量,在回调函数中改变这个变量的值,在exec执行完毕之后判断变量的值是否被改变,这样就可以知道是否查询到了值。这样可以避免某些错误。

        例如我在某个程序中写的代码:

static int callback_sqlite(void * data,int argc,char **argv,char **azColName){
    int i=0;
    #ifdef _DEBUG_
    printf("进入回调函数\n");
    #endif
    string keys[]={"word","phonetic","pos","acceptation","orig","trans"};
    for(i=0;i<argc;i++){
        #ifdef _DEBUG_
        printf("内存地址:%p\n",argv);
        printf("数据库查询中:%s\n",argv[i]);
        #endif
        (*(map<string,string>*)data).insert(pair<string,string>(keys[i],argv[i]?string(argv[i]):string("NULL")));
    }
    #ifdef _DEBUG_
    printf("退出回调函数\n");
    #endif
    (*(map<string,string>*)data)["isExistWord"]="true";
    return 0;
}

Interpretation inquire_core(sqlite3 * db,string word){
    Interpretation tempTransDataObj;
    char *ErrorInfo=0;
    int rc;
    map<string,string> WordData;
    WordData.insert(pair<string,string>("isExistWord","false"));
    string sql_cmd="select word,ps,pos,acceptation,orig,trans from words where word=\'";
    sql_cmd=sql_cmd+word+"\';";
    rc=sqlite3_exec(db,sql_cmd.c_str(),callback_sqlite,(void *)&WordData,&ErrorInfo);
    if(rc!=SQLITE_OK){
        cout<<"SQL ERROR:"<<ErrorInfo<<endl;
        sqlite3_free(ErrorInfo);
        exit(0);
    }else{
        #ifdef _DEBUG_
        cout<<"查询数据库成功"<<endl;
        #endif
    }
    sqlite3_close(db);
    map<string,string>::iterator it;
    it=WordData.find(string("isExistWord"));
    if(it->second!="true"){
        return tempTransDataObj;
    }
……
……
……
}

 

 

 

 

9.1-开学了

今天中午开始坐车,下午五点左右才到学校,注册完,进寝室收拾东西。

没有开始感觉的那么坑了,学校也看起来也不是那么黑暗了,在家就是闲了,才容易多想,一来到学校,感觉还可以,事情很多,又开始忙起来了。看到迎新的场面,想起来去年的自己,想起当时心里无比抗拒的感觉。

一年已经过了,时间不多了。