star

搜索

RSS

RSS Link

计数器

140176

代码整理器

2010年8月06日 23:55 | Comments(15) | Category:C语言 | Tags:

/*Neat Code v0.1 author:star date:2010
没有经过优化和维护,一次写成版本。为了方便地整理排版乱的代码。
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void NeatSpace(FILE *fin, FILE *fout);		//格式化空格字符
int  NeatType(FILE *fin, FILE *fout);		//格式化缩进
void Putlevel(FILE *out, int lv);			//输出缩进

int main(int argc, char *argv[])
{
	FILE *fin, *fout;
	char buf[255]= "t_";
	int  ErrorCode;

	if(1 == argc)
	{
		printf("Neat Code v0.1 -- star\n\n");
		printf("整理成Star喜欢的代码样式。\n");		
		printf("Usage:\nNeatCode source [destination]\n\n");
		printf(" source         指定要整理的文件。\n");		
		printf(" [destination]  可生成的目标文件。\n\n");	
		printf("如果没有输入目标文件,将会生成默认的。\n");					
	}
	else
		if(2 == argc)
		{
			if(!(fin = fopen(argv[1], "r")))
			{
				printf("错误001 - 无法打开%s文件。", argv[1]);
				return EXIT_FAILURE;
			}
			fout = fopen("~TEMP.NTC", "w");
			NeatSpace(fin, fout);
			fclose(fin);fclose(fout);
			fin = fopen("~TEMP.NTC", "r");
			strncpy(buf+2, argv[1], 253);
			if(!(fout = fopen(buf, "w")))
			{
				printf("错误002 - 创建%s文件失败。", buf);
				return EXIT_FAILURE;
			}
			ErrorCode = NeatType(fin, fout);
			fclose(fin);fclose(fout);
			system("del ~TEMP.NTC");
			if(ErrorCode) printf("错误005 - 所格式化的代码不标准 代码%d。", ErrorCode);
			else printf("成功执行!");
		}
		else
			if(3 == argc)
			{
				if(!(fin = fopen(argv[1], "r")))
				{
					printf("错误001 - 无法打开%s文件。", argv[1]);
					return EXIT_FAILURE;
				}
				fout = fopen("~TEMP.NTC", "w");
				NeatSpace(fin, fout);
				fclose(fin);fclose(fout);
				fin = fopen("~TEMP.NTC", "r");
				if(!(fout = fopen(argv[2], "w")))
				{
					printf("错误003 - 创建新的%s文件失败。", argv[2]);
					return EXIT_FAILURE; 
				}
				ErrorCode = NeatType(fin, fout);
				fclose(fin);fclose(fout);
				system("del ~TEMP.NTC");
				if(ErrorCode) printf("错误005 - 所格式化的代码不标准 代码%d。", ErrorCode);
				else printf("成功执行!");
			}else
			{
				printf("错误004 - 无效的命令。");
			}

			return EXIT_SUCCESS;
}

void NeatSpace(FILE *fin, FILE *fout)
{
	char ch = fgetc(fin);
	short cflag = 1;

	while(!feof(fin))
	{
		if(ch == '/' &&  fputc(ch, fout) && (ch=fgetc(fin)))
		{
			if(ch == '/' && fputc(ch, fout))
				while((ch=fgetc(fin)) != '\n') fputc(ch, fout);
			else if(ch == '*' && fputc(ch, fout))
				while((ch=fgetc(fin)) != '/') fputc(ch, fout);
		}
		if(ch == '\n' && (cflag = 1) && fputc(ch, fout))
		{
			ch = fgetc(fin);
			while(!feof(fin) && ch == '\n' || ch == ' ' || ch == '\t') ch = fgetc(fin);
			continue;
		}
		if(ch == ' ' || ch == '\t')
		{
			if(cflag == 0) fputc(ch, fout);
			while(ch == ' ' || ch == '\t') ch = fgetc(fin);
			continue;
		}
		else
		{
			if (ch != '{') cflag = 0;
			do{fputc(ch, fout);ch = fgetc(fin);}
			while(ch != '\n' && ch != ' ' && ch != '\t');
		}
	}
}

int NeatType(FILE *fin, FILE *fout)
{
	char ch = fgetc(fin);
	short IsTop = 1;
	signed int level = 0;

	if(ch == '\n') ch = fgetc(fin);
	while(!feof(fin))
	{
		while(ch != '\n' && ch != '{' && ch != '}')
		{
			IsTop = 0;
			fputc(ch, fout);
			ch = fgetc(fin);
		}
		if(ch == '\n' && (IsTop = 1))
		{
			fputc(ch, fout);
			ch = fgetc(fin);
			if(ch != '}')
				Putlevel(fout, level);
		}else
			if(ch == '{')
			{
				++level;
				if(!IsTop) fputc('\n', fout);				
				while(ch = fgetc(fin))
					if(ch == ' ' || ch == '\t');
					else if(ch == '\n') {fputc('{', fout);break;}
					else
					{
						Putlevel(fout, level-1);
						fputc('{', fout);
						fputc('\n', fout);
						break;
					}
				Putlevel(fout, level);				
			}else
				if(ch == '}')
				{
					--level;
					if(!IsTop) fputc('\n', fout);
					Putlevel(fout, level);
					fputc('}', fout);
					ch = fgetc(fin);
				}		
	}
	return level;
}

void Putlevel(FILE *out, int lv)
{
	if(lv > 0)
		while(lv--) fputc('\t', out);
}

上次不小心删了,再发一次吧。

求一个数是第几个排列数

2010年8月06日 00:47 | Comments(81) | Category:C语言 | Tags:

根据康托展开公式:$$C = \left\sum_{i=1}^{n}a_i(i-1)!\right$$

a[i]为第i个数比后面的都小的个数。

#include <stdio.h>
#include <string.h>
int FAC[10] = {1,1,2,6,24,120,720,5040,40320,362880};
int CantorExp(char *s, int n)
{
	int i, j, t, num = 0;
	for(i = 0; i < n; ++i)
	{
		t = 0;
		for(j = i+1; j < n; ++j)
			if(s[j] < s[i])
				++t;
		num += FAC[n-i-1]*t;
	}
	return num+1;
}
int main(int argc, char *argv[])
{
	char s[] = "1324";	//输入一个排列数的字符串序列 
	printf("%d", CantorExp(s, strlen(s)));
	return 0;
}

 

求平面最近点对

2010年8月04日 03:33 | Comments(44) | Category:C语言 | Tags:

对于平面上N个点,求其中两个距离最近的点。输入格式:点的个数N,然后是N个坐标即可计算出。

#include <stdio.h>
#include <math.h>
#include <assert.h>
#include <stdlib.h>

struct pos {double x, y;};
typedef struct pos Pos;
Pos p[100000];
int d[100000];
double eps = 0.00001;

int cmp_x(const void *p, const void *q)
{
	double tmp=((Pos*)p)->x-((Pos*)q)->x;
	if(tmp>0) return 1;
	else if(fabs(tmp)<eps) return 0;
	else return -1;
}

double Dest(Pos p2, Pos p1)
{
    return ((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x));
}

double Min(double a, double b)
{
    return a < b ? a : b;
}

int cmp(const void *a, const void *b)
{
     return(*(int *)a-*(int *)b);
}

double NSP(int left, int right)
{
    double m1, m2, m3 , res;
    int i, j, ix, mid;
    if(right - left == 1)
        return Dest(p[right], p[left]);
    else if(right - left == 2)
    {
        m1 = Dest(p[left], p[left+1]);
        m2 = Dest(p[left], p[left+2]);
        m3 = Dest(p[left+1], p[left+2]);
        return Min(m1, Min(m2, m3));
    }
    mid = (left+right)/2;
    res = Min(NSP(left, mid), NSP(mid+1, right));
    
    ix = 0;
    for(i = mid; i>=left && p[mid].x-p[i].x < res; --i)
        d[ix++] = i;
    for(i = mid+1; i<=right && p[i].x-p[mid+1].x < res; ++i)
        d[ix++] = i;
    qsort(d, ix, sizeof(d[0]), cmp);
    for(i = 0; i < ix; ++i)
        for(j = i+1; j<ix && j<i+4 && p[d[j]].y-p[d[i]].y < res; ++j)
            res = Min(res, Dest(p[d[j]], p[d[i]])); 
    return res;
}

int main(void)
{
    int N, i;
    while(scanf("%d", &N), N)
    {
    	assert(N!=1 && N<100000);
        for(i = 0; i < N; ++i)
            scanf("%lf %lf", &p[i].x, &p[i].y);
            
        qsort(p, N, sizeof(p[0]), cmp_x);
        printf("%.2lf\n", sqrt(NSP(0, N-1)));
    }
    return 0;
}

用的是分治法。

求一个数的二进制有多少个1?

2010年8月03日 02:29 | Comments(1) | Category:C语言 | Tags:

/*author:Star date:2010-08-02*/
#include <stdio.h>
#include <assert.h>

int CntBit(unsigned int n)	//分治思想
{
	n = ((n & 0xaaaaaaaa) >> 1 ) + (n & 0x55555555);
	n = ((n & 0xcccccccc) >> 2 ) + (n & 0x33333333);
	n = ((n & 0xf0f0f0f0) >> 4 ) + (n & 0x0f0f0f0f);
	n = ((n & 0xff00ff00) >> 8 ) + (n & 0x00ff00ff);
	n = ((n & 0xffff0000) >> 16) + (n & 0x0000ffff);
	return n;
}

int main(int argc, char *argv[])
{
	unsigned int N;
	int i, j;
	scanf("%u", &N);
	printf("%u:", N);
	i = CntBit(N);
	assert(i >= 0 && i <= 32);
	for(j = 31; j >= 0; --j)
		printf("%d", N&(1<<j) ? 1 : 0);	
	printf("\nhave %d bit that are \'1\'", i);
	return 0;
}

这里数以$$2^{32}-1$$的大小范围为例。

高精度除法器

2010年8月02日 02:41 | Comments(3) | Category:C语言 | Tags:

/*高精度除法器 v0.1 Author:star date:2010
*可以计算无限循环小数,循环部分用括号表示

*因为整数除法最终肯定会循环,所以输出是有穷的
*一些例子:
*1/3 = 0.(3)
*22/5 = 4.4
*1/7 = 0.(142857)
*2/2 = 1.0
*3/8 = 0.375
*输入格式:数字1+/字符+数字2+回车 
*输入例子:45/56
*输出结果:0.803(571428)
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <memory.h>
#define  BIT 100000 //除数与被除数范围都为100000 

int main(void)
{
	int N, D, Mods[BIT+100];
	char Ans[BIT+100];
	int i, j, st, ed, mod, cnt, Flag, tp , bt;
	char PreChar[100];
NEXT:
	memset(Mods, 0, sizeof(Mods)); //初始化内存 
	memset(Ans,  0, sizeof(Ans));
	memset(PreChar, 0, sizeof(PreChar)); 

	scanf("%d/%d", &N, &D); //输入
  
	assert(N >= 1 && N <= BIT);  //输入限制的数字和范围 
	assert(D >= 1 && D <= BIT);
	Mods[N] = cnt = Flag = 1; //初始化 
	if(!(N % D)) //整除了直接输出
	{
		printf("%d.0\n", N/D);
		goto NEXT;
	}
	if(N < D) //计算小数点前
	{
		PreChar[0] = '0';
		PreChar[1] = '.';
	}
 	else
 	{
 		tp = N / D;
  		bt = log10(tp);
		PreChar[bt+1] = '.';
  		for(i = bt; i >= 0; --i)
  		{
   			PreChar[i] = tp % 10 + '0';
   			tp /= 10;
  		}
  		N %= D;
  		PreChar[i] = '.';
	}
 	i   = 0;
 	mod = 100009; //Magic Number
 	while (!Mods[mod]) {  //计算小数点后的除法
  		Mods[mod] = cnt;
  		++cnt;
  		N        *= 10;
  		Ans[i++]  = N / D + '0';
  		N =  mod  = N % D;
 	} 
 	//寻找开始循环与结束循环
 	ed = cnt - 1;
 	st = Mods[mod];
 	//整除清0
 	if(Ans[ed-1] == '0' && Mods[0])
 	{
  		Flag      = 0;
  		Ans[ed-1] = '\n';
 	}
 	//输出
 	printf("%s", PreChar);
 
 	for(j = 0,i = 1; i < st; ++i)
  		if(Ans[i-1])
  			printf("%c", Ans[i-1]);
 	if(Flag) 
  		printf("(");
 	for(j = i; Ans[j-1]; ++j)
  		printf("%c", Ans[j-1]);
 	if(Flag) 
  		printf(")\n");
 	goto NEXT;
}