水题之 蛇形数组问题

发表于 由
回复

题目：


在n*n的方阵填入1,2,3……n*n.最后形成蛇形。例如n=4时的方阵为：其中（n<=8）
10 11 12 1
9 16 13 2
8 15 14 3
7 6 5 4

突然对这个题目感兴趣是某天看到姬加有人问到蛇形数组的问题，然后我找到了这个地址看题目，还参考了这里，我自己做的话，确实是没想到用机器人探路的方法，老想着手工硬编码确定填充下标逻辑，╮(￣▽￣")╭。我个人认为我的方法又比上面提到那个参考连接的做的又稍微好些哦，因为限制了while循环的次数，具体请直接看代码啦。这道题目感觉对数组的下标加强了理解，然后还提出了一个不错的思想，用走迷宫或者探路的方式来填充数组。下次试试Z字形的数组填充。

#include <stdio.h>
#include <stdlib.h>
 
int main(void){
	int n,i,j,k,value;
 
	printf("endter dimension:\n");
	scanf("%d",&n);
 
	/*基本的检测，好吧，我懒得防
	 * 试图输入100+的人。。*/
	if( n<=0){
		fprintf(stderr,"dimension must be positive!\n");
		exit(1);
	}else if( 20<n ){
		fprintf(stderr,"(\"▔□▔)个人强烈建议乃不要输入这么大的数字，在普通终端无法整齐打印\n");
	}
 
	/*霍霍霍，C99的变长数组*/
	int arr[n][n];
	for(i=0;i<n;++i){
		for(j=0;j<n;++j)
			arr[i][j] = 0;
	}
 
	/****************************************/
	/*这里有陷阱，y中-1表示的并非像坐标轴那 */
	/* 样的为下，而是上，因为正常的数组是逐 */
	/* 行增加行号的！所以并不是down,left,up */
	/* right ,应该是 up,left,down,right		*/
	/* 顺时针方向							*/
	/****************************************/
/*
	[0][0] -->--right---->[0][n-1]
	人						 |
	|						 |
	|						 |
	up						down
	|						 |
	人	 					 |
	|						 |
	[n-1][0]<----left--<--[n-1][n-1]
 
*/
 
	/********************************/
	/*	顺时针方向					*/
	/*  down , left , up , right	*/
	/*    0	 ,  1   ,  2 , 3		*/
	/********************************/
/*	int xd[]	= {1,0,-1,0};
	int yd[]	= {0,-1,0,1};
	i	= 0;
	j	= n-1;
	k	= 0;
*/
	/* 从左下角开始*/
	i	= n-1;
	j	= 0;
	k	= 2;
 
 
	/********************************/
	/* counterclock					*/
	/* left,down,right,up  			*/
	/*   0 ,  1  , 2  , 3 			*/
	/* k应当选择正确的起始方向的序号*/
	/* 比如从右上角开始，则起始方向 */
	/* 为左，方向代表号为0			*/
	/********************************/
	int  xd[]	= {0,1,0,-1};
	int  yd[]	= {-1,0,1,0};
	i	= 0;
	j	= n-1;
	k	= 0;
 
	value		= 2;
	arr[i][j]	= 1;
	while(value <= n*n){
		i += xd[k];
		j += yd[k];
		if( i<n && j<n && 0<=i && 0<=j && (arr[i][j] == 0))
			arr[i][j] = value++;
		else{
			i -= xd[k];
			j -= yd[k];
			k  = (k+1)%4;
			/* 这里的巧妙在于，合理构造xd,yd数组
			 * 使得刚好按照所选的顺序（顺时针或者
			 * 逆时针）所需的方向前进。这样就不用
			 * 继续滚到下一个while循环做无谓的测试
			 * 了，限制while循环严格循环n^2次。这
			 * 也就是为什么前面强调起始方向的序号
			 * k一定要正确。*/
			i += xd[k];
			j += yd[k];
			/*if(!( i<n && j<n && 0<=i && 0<=j && (arr[i][j] == 0)))
				fprintf(stderr,"Impossible\n");
				// used for debug
			*/
			arr[i][j] = value++;
		}
	}
 
	/*打印出数组*/
	for(i=0;i<n;++i){
		for(j=0;j<n;++j){
			if( n<10 )
				printf("%2d ",arr[i][j]);
			else
				printf("%3d ",arr[i][j]);
				/*大于等于10的时候会出现三位数，故以3位补齐*/
		}
		printf("\n");
	}
 
	return 0;
}

顺便啦，Z形的数组问题：

int main(void){
	int n,i,j,k,value,ti;
	printf("enter array dimension:\n");
	scanf("%d",&n);
 
    /*霍霍霍，C99的变长数组*/
    int arr[n][n];
    for(i=0;i<n;++i){
        for(j=0;j<n;++j)
            arr[i][j] = 0;
    }  
 
	/* 坐标的规律为 (0,0)
	 * (1,0)(0,1)
	 * (2,0)(1,1)(0,2)
	 * (3,0)(2,1)(1,2)(0,3)...*/
	/*真正的算法开始了*/
	value		=	2;
	arr[0][0] 	=	1;
 
	while( value <= n*(n-1)/2 ){
		for(i=1;i<=n-1;++i){
			ti = i;
			for(j=0;j<=i;++j){
				arr[ti--][j]	=	value++;
			}
		}
	}
 
	/*打印数组*/
	/*每行长度从n逐渐递减至1*/
	for(i=0,k=n;i<n;++i){
		for(j=0;j<k;++j){
			printf("%2d ",arr[i][j]);
		}
		--k;
		printf("\n");
	}
	return 0;
}

开灯问题与memset

发表于 由
回复

问题描述：有N个灯，（每个灯只有一个开关，按一下开，再按一下关）来了K个人，第一个人把所有灯都打开，第二个人按下了所有编号为2的倍数的灯的开关，第三个人按下所有编号为3的倍数的灯的开关……按此规律。问最后那些灯亮着？

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
int main(void){
    int ln,pn,i,j,k;
    printf("Enter number:\n");
    scanf("%d %d",&ln,&pn);
 
    if( ln<=0 || pn<0){
        fprintf(stderr,"Cannot be negative!\n");
        exit(1);
    }   
 
    int *optr = (int *)malloc( sizeof(int) * ln);
    if( optr == NULL){
        fprintf(stderr,"Malloc failed\n");
        exit(1);
    }   
 
    int *ptr = optr;
    memset(ptr,1,ln);
    for(i=0;i<ln;++i){
        for(j=2;j<=pn;++j){
            if ((i+1) % j == 0)
                *(ptr + i)  = !(*(ptr+i));
        }   
    }   
    for(i=0;i<ln;++i){
        if (*(ptr+i) == 1)
            printf("%d ",i+1);
    }
    printf("\n");
 
    free(optr);
    return 0;
}

结果自然就2B了…

root@natty-150:/pr/c# ./light_on_3
Enter number:
7 3
3 4

想来想去几个for都确定木有问题啊，为毛不能用memset呢。果断gdb看了下：
立马怒懂了，认真看了下资料说：
memset功 能: 设置s中的所有字节为ch, s数组的大小由n给定
用法: void *memset(void *s, char ch, unsigned n)
嗯，所以其实呢，以int单位大小分配的空间是需要慎用memset的！一般memset只与char数组等搭配。而要修改其实也不难，把memset值从1改成0就好了。这正是这篇里 http://blog.csdn.net/oosuifengoo/article/details/7062588 歪打正着的原因。。下面是OK的代码，
输入：7 3
输出：1 5 6 7

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main(void){
    int ln,pn,i,j,k;
    printf("Enter number:\n");
    scanf("%d %d",&ln,&pn);
 
    if( ln<=0 || pn<0){
        fprintf(stderr,"Cannot be negative!\n");
        exit(1);
    }   
 
    int *optr = (int *)malloc( sizeof(int) * ln);
    if( optr == NULL){
        fprintf(stderr,"Malloc failed\n");
        exit(1);
    }   
 
    int *ptr = optr;
    memset(ptr,0,ln);
    for(i=0;i<ln;++i){
        for(j=1;j<=pn;++j){
            if ((i+1) % j == 0)
                *(ptr + i)  = !(*(ptr+i));
        }   
    }   
    for(i=0;i<ln;++i){
        if (*(ptr+i) == 1)
            printf("%d ",i+1);
    }
    printf("\n");
 
    free(optr);
    return 0;
}

其实这个是我看到memset后写的，自己一开始写的是这个：

#include <stdio.h>
#include <stdlib.h>
 
int main(void){
	int light_num = 0;
	int people_num  = 0;
	int i	= 0;
	int j 	= 0;
	int k	= 0;
	int *t 	= 0;
	printf("enter 灯的数量和人的数量，以空格分隔\n");
	scanf("%d %d",&light_num,&people_num);
	if( light_num<=0 || people_num<0 ){
		printf("Invalid number\n");
	}
	int *ptr  =(int *)malloc( sizeof(int)*light_num );
	int *optr = ptr;
 
	if (ptr == NULL)
		exit(1);
	for(i=0;i<light_num;++i){
		*(ptr+i) = 1;
	}
 
	ptr	=	optr;
	for(j=2;j<people_num+1;++j){
		for(k=1;k*j<light_num;++k){
			t = ptr+k*j-1;
			if (*t == 1)
				*t = 0;
			else if(*t == 0)
				*t = 1;
 
	//		*t = !t;
		}
	}
 
	/*输出亮着的灯*/
	ptr = optr;
	for(i=0;i<light_num;++i){
		if ( *(ptr+i) == 1 ){
			printf("%d ",i+1);
		}
	}
 
	printf("\n");
	return 0;
}

略为2B…

GDB 调试hostentry问题

发表于 由
回复

对于一个结构struct gdb调试是非常方便的。不过前提是你必须要用gcc -g编译程序，这样程序才携带有符号表，调试才能各种爽。

比如查看结构的定义：

这里顺便吐槽下，伤不起的hostent定义啊！ h_addr_list居然是 char **?!不是struct in_addr **么！！

更方便的是直接打印出结构体全部的内容！再也不用自己写printf鸟。

这里遇到了诡异的情况：

#include <stdio.h>
#include <stdlib.h>
#include <arpa/inet.h>
#include <netdb.h>
 
int
main(int argc, char *argv[]){
	struct hostent *h;
	if (argc != 2){
		printf("usage: %s <domain name>\n", argv[0]);
		exit(0);
	}
	if (( h = gethostbyname(argv[1])) == NULL){
		fprintf(stderr, "Cannot get host name\n");
		exit(0);
	}
	char *ip_addr1 = inet_ntoa(*((struct in_addr *)h->h_addr_list));
//	char *ip_addr2 = inet_ntoa(*((struct in_addr *)h->h_addr));
	printf("ip1 addr is: %s\n",ip_addr1);
//	printf("ip2 addr is: %s\n",ip_addr2);
	return 0;
}

这段代码编译后运行./gethostinfo www.100steps.net
结果居然是：ip1 addr is: 4.177.141.9

而把两行被注释掉的加入代码后再编译运行，结果又都是对的！

用GDB探索stack frame

发表于 由
回复

样例代码如下：

#include<stdio .h>
#include<stdlib .h>
int func1(int arg1, char *arg2, char arg3)
{
	printf("in func1: %d %s %c\n",arg1,arg2,arg3);
	return 1;
}
int func2()
{
	printf("in func2\n");
	return 2;
}
int main(int argc, char **argv)
{
	int val1 = func1(5, "This is a test", 'a');
	int val2 = func2();
	printf("in main\n");
	return 0;
}
</stdlib></stdio>

使用gcc编译：
gcc -o rcbj_test rcbj_test.c 继续阅读 →

GDB初试

发表于 由
回复

[0x00]

gdb是个神马东西

估计大致都还是听说过这货的。不过嘛，至于是否经常使用，那就╮(╯▽╰)╭

[0x01]

一些用法

设置断点

(gdb) b main
Breakpoint 1 at 0×8048420: file lg_test.c, line 12.
(gdb) b foo
Breakpoint 2 at 0x80483fa: file lg_test.c, line 6.

然后用run命令让程序跑到断点处：
gdb_run

查看内存用x命令：

x/<n/f/u> <addr>网上都是这么表达滴：

n  是一个正整数，表示显示内存的长度，也就是说从当前地址向后显示几个地址的内容。
f  表示显示的格式，参见上面。如果地址所指的是字符串，那么格式可以是s，如果地十是指令地址，那么格式可以是i。
u  表示从当前地址往后请求的字节数，如果不指定的话，GDB默认是4个bytes。u参数可以用下面的字符来代替，b表示单字节，h表示双字节，w表示四字

比如我要按4个字节一起显示某个地址的十进制值，则：可以gdb_x_当然其实跟用p &i直接显示i地址的值是一样的。p命令默认会按照变量类型显示？gdb_x_p_i

[0x0x] other stuffs

即使你用-q选项（quite不输出版本信息）启动，gdb仍然会给出一堆的warning：gdb_warning_png

/root/.gdbinit:1: Error in sourced command file:
Ambiguous set command “dis intel”: disable-randomization, disassemble-next-line, disassembly-flavor, disconnected-tracing…

据说是因为dis intel 命令过时了。

C的local variable问题

发表于 由
回复

在某个地方遇到这么个代码，当时我正在在gcc的function return local variable address的相关内容。（嗯，我知道那是不对的，然后好奇在没有gc机制下，c的栈要怎么处理）于是看到了下面这个代码。无法解释。在plus上问了，感觉Larry Li的解释没到点上。

#include <stdio .h>
 
void foo(void)
{
	int i;
	printf("%d\n", i);
	i = 777;
}
 
int main(void)
{
	foo();
	foo();
	return 0;
}
</stdio>

继续阅读 →

Bash 经验记录

发表于 由
回复

echo -n
“-n” 选项可以让echo不自动输出换行符’\n’
echo -en "\e[32m\e[1mUsername:\e[0m"
打印高亮绿色的字符串“Username”
echo -e "\e[31m\e[1musername exist already !!\e[0m"
打印红色

关于exit 1 有个很经典的问题：

n 'p;n' $account_file |while read exist_username
do
if [ $exist_username == $username ];then
# print red warning info
echo -e "\e[31m\e[1musername exist already !!\e[0m"
exit 1
fi
done

像上面那样是不会退出的！因为while是用一个子shell来跑的！exit退出的只是子shell而已。当时纠结了我一下。。还好在伟大的SO找到了答案。那位哥的情况简直跟我的一模一样.╮(￣▽￣")╭ 多少青年在while里的if天真的exit 1 试图结束脚本。。解决办法也很简单，只需要在上面代码下面添加 $? != 0 ] && exit 1 做检测就好了。
另外，这篇关于exit的文章写得挺不错的。

Oreilly的乌龟shell书里2.4 节提到说 "#! /bin/sh -" 比较安全，可以某种程度避免欺骗式攻击（spoofing attack），但没有解释什么是所谓的spoofing attack. 找了一下在这里有人提到说

This would be important if you are using setuid scripts. But you shouldn't assign setuid permissions to a script anyway.

重拾libpcap

发表于 由
回复

首先要安装libpcap库：

apt-get install libpcap-dev

官网的一个教程里的基本代码

#include <stdio.h>
#include <pcap.h>
 
int main(int argc, char *argv[])
{
	char *dev, errbuf[PCAP_ERRBUF_SIZE];
 
	dev = pcap_lookupdev(errbuf);
	if(dev == NULL){
		fprintf(stderr, "Couldn't find default device:%s\n", errbuf);
		return(2);
	}
	printf("Device: %s\n", dev);
	return(0);
}

然后编译

gcc p2.c -o p2 -lpcap

吐槽一下为什么我们博客都转跳到某红彤彤网站

发表于 由
4

当时在群上问了下，碧龙跟我说已经去掉默认转跳”红彤彤主旋律”网站了。=_,=
然后我一直以为是是通配符（wild card) “*”的原因。好吧，今天我用irix.me被转跳了。。囧啊，跟庞大仙的一样了。。（还好你们都不知道。霍霍霍~~） 于是终于忍不住要去改通配符了，于是顺便突然想起了用”.irix.me”可以同时匹配 *.irix.me 和 irix.me本身，╮(￣▽￣”)╭ 人的记忆不靠谱啊，当时改完庞聪的马上就忘了这回事了。关于server的nginx文档在这里。

A special wildcard in the form “.nginx.org” can be used to match both the exact name “nginx.org” and the wildcard name “*.nginx.org”.

然后还是很奇怪，如果是我切割了虚拟主机文件导致顺序匹配的问题也不至于从我的i直接跳到t啊。。然后再一看”红彤彤主旋律”网站条目。。

擦。。额，截图是我注释掉后截的。

想起来当时直接在官网文档看到是说用default_server指定默认指向：

If the “Host” header line does not match any server name, or the request does not contain this line at all, then nginx will route the request to the default server. In the configuration above, the default server is the first one — which is nginx’s standard default behaviour. If you do not want the first server listed to be the default server, you may set it explicitly with the default_server parameter in the listen directive:

server {
listen 80 default_server;
server_name nginx.net www.nginx.net;
…
}

，grep了一下没看到就纠结了。。今天再去看突然注意到后面小小的提醒

The default_server parameter has been available since version 0.8.21. In earlier versions the default parameter should be used instead.