Dec 26
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#define P(a, b) printf(#b ": %" #a "\n", b)
#define Ps(a, c, b) P(a, (c)->b)
#define alloc(name, type, n) type *name = (type *) malloc(sizeof(type) * (n))
#define allocs(name, type, n) alloc(name, struct type, (n))

int main ()
{
    time_t t1 = time(NULL);
    P(ld, t1);

    struct timeval tv1;
    gettimeofday(&tv1, NULL);
    Ps(ld, &tv1, tv_sec);
    Ps(ld, &tv1, tv_usec);

    /*
     * //t1 += 8 * 3600;
     * struct tm *tm1 = gmtime(&t1); //标准时间
     */
    struct tm *tm1 = localtime(&t1); //本地时间
    Ps(d, tm1, tm_sec);
    Ps(d, tm1, tm_min);
    Ps(d, tm1, tm_hour);
    Ps(d, tm1, tm_mday);
    Ps(d, tm1, tm_mon+1); //0-based
    Ps(d, tm1, tm_year+1900); //从1900年开始, 0-based

    allocs(tm2, tm, 1);
    tm2->tm_sec = 0;
    tm2->tm_min = 0;
    tm2->tm_hour= 0;
    tm2->tm_mday= 1;
    tm2->tm_mon = 0;
    tm2->tm_year= 70;
    tm2->tm_isdst = 0;
    time_t t2 = mktime(tm2);
    //t2 += 3600 * 8; //mktime是本地时间
    P(ld, t2);

    P(s, asctime(tm1)); //标准时间
    P(s, ctime(&t1)); //本地时间

    alloc(buf, char, 100);

    strftime(buf, 100, "%Y-%m-%d %H:%M:%S", tm1); //标准时间
    P(s, buf);

    strftime(buf, 100, "%F %T", tm1); //标准时间, 格式和上面的一样
    P(s, buf);
    return 0;
}
Dec 26

方便写代码的宏... 不指定

felix021 @ 2009-12-26 17:39 [IT » 程序设计] 评论(3) , 引用(0) , 阅读(3850) | Via 本站原创
写代码的时候总是觉得printf打起来很麻烦,malloc的强制转换和sizeof很罗嗦,写几个宏,方便多了
#define P(a, b) printf(#b ": %" #a "\n", b)
#define Ps(a, c, b) P(a, (c)->b)
#define alloc(name, type, n) type *name = (type *) malloc(sizeof(type) * (n))
#define allocs(name, type, n) alloc(name, struct type, (n))
Dec 13
由于上次和slyar同学提起这个问题,所以才想着还是自己再写一下,而且其实还有自己没解决的问题,希望能抛砖引玉。

剧透
本篇未解决的问题是:在n个数字里面,如果只有3个数字是没有凑对的,能否用O(n)的方法找出来?超过3个又远小于n个的情况呢?

===

WOJ上有2道连在一起的题目,很赞。

找不同:http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1202
找相同:http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1203

找不同:给你n*2+1个数,其中有n对是一样的,让你找出没有相同数字的那一个(真寂寞)。
如果我们能把所有的数字按大小排序,那么只要两个两个拿出来
第一次出现不一致的情况或者剩下最后一个数字的情况,就是找到寂寞数字了时候。
可是这样效率太低,就算用基数排序,那个常数也是够大的。
换个思路,由按位异或操作的性质可以知道 a | a = 0 且 (a | b) | c = a | (b | c)
也就是说,按位异或这个“按位模2加”操作的性质是同一个数与自身异或得0,且该操作是可交换的。
所以如果我们将所有数字串起来异或,其实就等于把所有数字排序后再串起来异或。
所有相同的数字想异或都得0,最后异或的结果就是最寂寞的那个。。

找相同:有一组数,很多很多个数,里面有一个数出现了超过一半次,请你把它找出来
可以证明,如果反复地执行这一操作【从这2*n+1个数里面取出两个数ab,如果a,b相同,放回去,如果a,b不同,都舍弃】直到剩下来的所有数字都相同(这一定是可以达到的)。所以只要设计一个最高效的方式来实现这个过程就行了。
最简单的方式是O(n)的,用栈。伪码如下
init stack(s)
for x in a[1..n]
    if empty(s) or s.top() == x
        s.push(x)
    else
        s.pop()
return s.top()


如果有同学看看1204的话,就会知道,这题是
继续找相同:http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1204
描述:有 n 个整数, 其中有且仅有一个整数出现了 >= n/2.0 次 (n<=500000)
跟前面那道题的只有一点点的区别,多了一种情况就是,有一个数字可能正好出现一半次。
直接用上面那种方法肯定没法处理了,但是只要稍微想想,其实还是很容易的:
用上面的方法处理前1~n-1个数字,到了最后一个数字的时候,看看和栈里面那个数字是不是一样
如果一样,说明这个数字出现了超过一半次,输出
如果不一样,那么栈里肯定只剩下一个数字,能出现一半次的,肯定是这两个数字之一,重新扫一次数组就行了。

WOJ关于找相同和不同的貌似就只有三道题,但是“继续”其实还没完。

继续找不同:有2n个数字,其中2n-2个数字是两两凑对的,剩下两个数字很寂寞,请找出来。
这题和前面的找不同也很像,解决方法是可以“复用”的。
以前的一篇日志里面有:http://www.felix021.com/blog/read.php?1243
解法是momodi给出的,将全部数字异或以后等到的C = A ^ B != 0 (若C==0则A==B,不符合要求)
然后扫描C的每一bit,如果bit[k] == 1,那么将C和给出的数据中所有bit[k] == 1的整数异或
得出的就是其中一个数字A,然后A ^ C = B
这种解法也是O(n)的,只需要扫描两遍,还是比较快的。

-------------------------------------
最后,重点:
如果是3个数,或者更多一些,有没有O(n)的解法?
当然,用O(n)的基数排序处理以后再遍历,的确是O(n)的效率,但是就是效率太低了,而且需要多次遍历。
假设数字的量超过1000亿,需要存放在硬盘中(也就是扫描次数越少越好),这该怎么办呢?

心里已经有些想法了,不过暂时不想写出来,再想想明白。
如果哪位大牛有好的想法,希望互相交流一下:)
Dec 10

记录PHP的一个trick 不指定

felix021 @ 2009-12-10 10:23 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(3687) | Via 本站原创
在int32(64位机器则为int64)的范围内的证书作为数组索引来存储数据的话,
在php中,会自动将这种可以转换成int的字符串转换成int作为索引使用。

以下面这一段脚本的输出来说明这个问题:

<?php
$arr = array(
        123 => 'a',
        '123' => 'b',
        0123 => 'c',
        '0123' => 'd',
        );
var_dump($arr);
?>
输出:
array(3) {
  [123]=>
  string(1) "b" //第一个123的a消失了,却出来了一个b,说明"123"在索引中被当作int处理了,并覆盖了之前123索引对应的值
  [83]=>  //0123是八进制的83
  string(1) "c"
  ["0123"]=> //字符串
  string(1) "d"
}
Nov 22

类对象成员函数指针 不指定

felix021 @ 2009-11-22 19:03 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(5599) | Via 本站原创
不解释,就让你看得蛋疼。
#include <iostream>
using namespace std;

class T {
typedef void (T::*Tptr)(void);
    Tptr p;
public:
    void a() { cout << "a" << endl; }
    void b() { cout << "b" << endl; }
    void call(Tptr _p) {
        p = _p;
        (this->*p)();
    }
};

int main() {
    T t1;
    t1.call(&T::a);
    t1.call(&T::b);
    return 0;
}
Nov 19

类TeX的UBB表格函数 不指定

felix021 @ 2009-11-19 02:29 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(2927) | Via 本站原创
引用
UBB内容为(开头那个下划线不需要加):
[_table]
l | r | l | c | r
左对齐|右对齐|左对齐|<a href="javascript:alert(12345)">居中啦啦啦</a>|右对齐
1|23|456|7890[newline]1234|0000
abcd|efg|hi|[-]|j
1|[-]|[-]|1|1
[/table]

效果:
左对齐 右对齐 左对齐 <a href="javascript:alert(12345)">居中啦啦啦</a> 右对齐
1 23 456 7890
1234
0000
abcd efg hi j
1 1 1


PHP代码:
function maketbl($str) {
    $str = str_replace("<br/>", "\n", $str);
    $str = str_replace("&#124;", "|", $str);
    $str = trim($str);
    $lines = explode("\n", $str);
    $firstline = explode("|", trim($lines[0]));
    $conf = array();
    foreach($firstline as $v) {
        switch($v) {
        case 'l':
            $conf[] = 'left';
            break;
        case 'r':
            $conf[] = 'right';
            break;
        case 'c':
            $conf[] = 'center';
            break;
        default:
            $conf[] = '';
        }
    }
    $ncols = count($conf);
    $nline = count($lines);
    $ret = '<table cellspacing="0" cellpadding="3" border="1">'. "\n";
    for ($i = 1; $i < $nline; $i++) {
        $line = trim($lines[$i]);
        if (empty($line)) continue;
        $line = explode("|", $line);
        $ret .= "<tr>\n";
        $next = 1;
        for ($j = 0; $j < $ncols; $j++) {
            if ($line[$j] == "[-]") {
                $next++;
                continue;
            }
            $td = $line[$j];
            //$td = htmlspecialchars($td);
            $td = str_replace("[newline]", "<br/>", $td);
            $ret .= <<<eot
<td align="{$conf[$j]}" colspan="{$next}">{$td}</td>

eot;
            if ($line[$j] != "[-]") {
                $next = 1;
            }
        }
        $ret .= "</tr>\n";
    }
    $ret .= "</table>";
    return $ret;
}
Nov 18

数据结构:栈 不指定

felix021 @ 2009-11-18 23:56 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(5536) | Via 本站原创
花点时间总结一下“栈”相关的内容。希望对于初学栈的同学会比较有帮助。

另外,其中涉及的一些内容也是书本上不会涉及到,或者是零零散散写出来的。看看总没坏处。

--------------传说中的分割线-------------

数据结构:栈

内容纲要
1. 什么是栈
2. 栈的实现(C语言)
  a) 数组实现
  b) 单链表实现
  c) 两种实现的对比
3. 栈的应用
  a) 在函数调用中的作用
  b) 在局部变量存储中的应用
    * 栈空间和系统维护的堆空间的对比
  c) 在算法中的应用
Nov 8

重温八皇后问题 不指定

felix021 @ 2009-11-8 13:58 [IT » 程序设计] 评论(3) , 引用(0) , 阅读(5361) | Via 本站原创
    如果从大一算起,写C已经有3年了。其实高中也写过,但是基本可以忽略不计。代码量,比起acm/icpc正规军来说,当然还是少得多;但是应该也有几万行了。写了这么多代码,也看了不少算法,感觉就是,这样的经验需要时间的积淀。曾经觉得很难的问题,现在已经在脑子里豁然开朗。就比如八皇后问题,上一次研究它,是2007年6月的事情。那会儿应该能想的清楚了,但是对于那时候的我而言,回溯算法仍然是比较难以理解的(记得有一次想写一个生成全排列的程序,写了半天都不对,最后还是让sandy写了一个标程抄了两遍,才逐渐理解)。差不多2年半过去了,再回首这个八皇后,发现思路非常清晰,很快就把代码写出来了。

    废话完回到这个问题上。它的两个难点在于:1. 如何判断某一个位置是否可以放置一个皇后;2. 回溯。

    如果给这个8*8的矩阵上个坐标,横向(rows)为i = 0 to 7,纵向(columns)为j = 0 to 7。那么可以发现,在每一条斜线(/)方向上,每一个格子的横纵坐标之和(i + j)是一个固定值,从左上到右下的斜线,其值依次是0~14 (0+0; 0+1,1+0; 0+2,1+1,2+0; ... ; 6+7,7+6; 7+7)。同样地,,在每一条反斜线(\)方向上,每一个格子的横坐标与纵坐标的关系是, (i + (7 - j))是固定值,从右上到左下的斜线,其值依次是0~14。

    因此,在开始寻找方案之前,给横、纵、斜线、反斜线方向各设置一个数组,所有元素初始化为0(表示可以放置),那么,在将皇后放置到(i, j)之前检查rows[i]、cols[j]、slash[i+j]、bslash[i+7-j]是否都为0,就可以判断这个位置能否放置皇后。由于放置的过程是从上到下一行一行放的,所以这个rows数组实际上可以去掉。这样第一个难点就解决了。(p.s. bslash -> backslash)

    第二个难点,回溯,这个我觉得不是很容易能说清楚的。简单地说,需要回溯的就是前面提到的cols/slash/bslash数组。一行一行地来:每一行从第一个位置开始查找,当找到一个有效位置,放置一个皇后,将对应的值置为1(以后的位置就可以检测是否可放),然后继续查找下一行的位置(递归调用);如果下一行没有合适的位置(递归返回),将对应的位置重置为0,然后查找这一行下一个位置。

    这个问题实在不是一个有难度的问题,我居然扯了这么多。可见我现在多闲啊。俗话说的好:经常扯蛋有助于预防蛋疼。

    下附代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 8

int count;
int rows[N],    cols[N],    slash[2 * N - 1], bslash[2 * N - 1];
//每行放的位置,纵向不可放,斜向不可放(/),斜向不可放(\)

void place(int i) {
    int j;
    for (j = 0; j < N; ++j) {
        if (cols[j] == 0 && slash[i + j] == 0 && bslash[i + (N-1) - j] == 0) {
            rows[i] = j;

            cols[j] = 1;
            slash[i + j] = 1;
            bslash[i + (N-1) - j] = 1;

            if (i == N - 1) {
                /*
                int k;
                for (k = 0; k < N; ++k) {
                    printf("%d ", rows[k]);
                }
                printf("\n");
                */
                count++;
            }
            else {
                place(i + 1);
            }

            //回溯
            cols[j] = 0;
            slash[i + j] = 0;
            bslash[i + (N-1) - j] = 0;
        }
    }
}

int main () {

    memset(rows, 0, sizeof(rows));
    memset(cols, 0, sizeof(cols));
    memset(slash, 0, sizeof(slash));
    memset(bslash, 0, sizeof(bslash));

    count = 0;
    place(0);
    printf("count = %d\n", count);
    return 0;
}
分页: 8/21 第一页 上页 3 4 5 6 7 8 9 10 11 12 下页 最后页 [ 显示模式: 摘要 | 列表 ]