存档

‘C’ 分类的存档

差分序列

2011年9月29日 8 条评论

不小心遇到一题4次求和，推公式推了好久。。想想实在是没有必要，每次遇到还得推一边实在是累。。所以，回来就写了一个差分的版本，单次计算的效率不比直接公式差，不容易出错，而且，再也不用蛋去推多项式公式了

至于什么是差分序列，这个我就不解释了，wiki上应该可以找到。我的写法是借鉴了牛顿插值的，使用了一个递推的写法（一般求多项式都会用这个， 比如4n^3 + n^2 + 2 * n + 3，一般写成 ((4n + 1) * n + 2) * n + 3）

初始化细节说明：order是生成的多项式的阶，请确保它大于或等于实际的多项式阶。order阶的多项式需要用order+1项进行init，请把这前order+1项存入数组cof中。最后调用init函数，就可以用calc来计算任意项了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

/******************************************************************************
  * Differential Sequence
  * init: O(order^2)
  * you should init the cof[i] with the value of i-th value of sequence
  * the sequene start from startfrom, default is 0, so a[0] is the first one
  * 	of sequence a
  * calc: O(order)
  ****************************************************************************/
 
const int ORDERLIM = 100;
 
double cof[ORDERLIM + 1];
int order;
const int startfrom = 0;
 
void init()
{
	int i, j;
	for(i = 1; i <= order; i++) {
		for(j = order; j >= i; j--) {
			cof[j] -= cof[j - 1];
		}
	}
}
 
double calc(double n)
{
	int i;
	double res = 0;
	for(i = order; i > 0; i--) {
		res += cof[i];
		res *= (n - i + 1 - startfrom) / i;	
	}
	res += cof[i];
	return res;
}
 
/******************************************************************************
  * MOD version of Differential Sequence
  * cof should not overflow MOD
  * MOD should should not less than order
  * MOD should be prime
  * need inverse in mod MOD system
  ****************************************************************************/
typec MOD = 1000000007;
typec cof[ORDERLIM + 1];
typec inv[ORDERLIM + 1];
int order;
const int startfrom = 0;
 
void init()
{
	int i, j;
	for(i = 1; i <= order; i++) {
		inv[i] = inverse(i, MOD);
		for(j = order; j >= i; j--) {
			cof[j] -= cof[j - 1];
		}
	}
}
 
typec calc(typec n)
{
	int i;
	typec res = 0;
	for(i = order; i > 0; i--) {
		res += cof[i], res %= MOD;
		res *= (n - i + 1 - startfrom) % MOD * inv[i] % MOD;
		res %= MOD;
	}
	res += cof[i], res %= MOD;
	while(res < 0) res += MOD;
	return res;
}
分类: ACM, C, Math 标签: ,

输出循环节，进制的游戏

2010年4月22日 2 条评论

首先给出一个特殊情况的分数m/n循环节输出(代码,基于小学就学过的除法笔算算法，p是进制，当然你可以全部用10替换)，我们先假设它的循环节是从小数点第一位开始（在下面我会用进制变换证明）

void printDecimalRec(int m,int n,int p) //这里假设m<n,且(n,p)=1,且输出省略“0.”
{
    int flag=m;
    do
    {
        m*=p;
        printf("%d",m/n);
        m%=n;
    }while(m!=flag);
}

分类: C, Cpp 标签:

指针的偏移

2010年4月1日 2 条评论


       如果你对指针有着更深的理解，你就会意识到，指针不仅仅是一个地址，它同时还具有一个偏移属性。

       指针的基本偏移就是地址自加之后和原地址的差。在一般情况下，这个差是由指针类型决定的，char的基本偏移是1个字节，int型是4个字节（32bit机中），比如对于int *p，p+1和p的物理地址差是4个字节，对于数组int a[3]，情况就少复杂，在使用中a是作为指针调用的，a的基本偏移是4个字节，但是你还可以对a进行如下操作&a，这个结果也是一个指针，所指向的地址跟a一样（数组首地址），但是基本偏移是不同的，这个偏移等于sizeof(int)*3,即3×4=12(其实就是sizeof(a))字节，加一后，它直接指向数组后面（已经在数组外了）。考虑二维数组的话，你会发现更好的结果，比如int a[3][7]，行宽是7，a的基本偏移就是4×7字节，*a是4字节，**a已经不是地址，它指向数组的元素，再看&a，跟一维的情况一样它指向数组后，偏移是4×7×3(即sizeof(a))。

       值得注意的是：以上对于数组的情况不适用于一般的指针，指针似乎只有单层次的偏移，而数组的作为指针引用的时候，偏移却是多层的。编译器似乎给了数组而外的属性，sizeof对数组的作用和对指针的作用是完全不同的。在使用指针对数组引用的时候（仅用数组名），会有很多额外的属性，而指针试图像数组般引用确实很困难的。

       我目前依然没有办法仅用指针构建多维数组（可以给出一个不连续的地址块，不能像二维数组般是一个连续的地址快,或者可以用一维模拟多维，但是它的引用比数组麻烦的多）。

分类: C 标签:

十进制以内的进制转换（递归C）

2010年3月1日 没有评论

给出一个tranp函数，该函数把10进制转化为p进制的输出

void tranp(int n,int p)
{
    if(n>p-1)
       tranp(n/p,p);
    printf("%d",n%p);
}

在给出p进制到十进制的函数

int tranpt(int n,int p)   //假设p小于10
{
    return n? tranpt(n/10,p)*p+n%10:0;
}

类似的有十进制到p进制的函数

int trantp(int n,int p)
{
    return n? trantp(n/p,p)*10+n%p:0;
}

如果要进行p进制数的运算，可以先在十进制运算，再转为p进制。

附加的给出个求n！的函数

int fact(int n)
{
    return n? n*fact(n-1):1;
}
分类: C 标签: