[TOC]
基本操作的威力
B. 将一个n元一维向量左旋转i个位置。例如，当n=8且i=3时，向量abcdefg旋转为defghabc。简单的代码使用一个n元中间向量在n步内完成该工作。你能仅使用10个额外字节的存储空间，在正比于n的时间内完成向量的旋转。
-
将x的前i个元素复制到一个临时数组，然后将余下的n-i个元素左移动i个位置，最后将最初的i个元素复制到x余下的位置。
-
定义一个函数将x左旋转一个位置（其时间正比于n）,然后调用函数i次，但该方法产生量过多的运行时间消耗。
-
杂技算法 -> 要在有限的资源内解决该问题，显然需要更加复杂的程序。有一个成功的方法有点像精巧的杂技动作：移动x[0]到临时变量t,然后移动x[i]到x[0],x[2i]移动到x[i] 以此类推（将x中所有下标对n取模），直到返回取x[0]中的元素，此时改为从t取值，然后终止过程。至此，一次移动结束。循环gcd(n,i)次即可，gcd为最大公约数。
-
求逆运算 -> x看作a,b两段,其中a的长度为i,旋转操作可化为
a -> a' b -> b'
ab=(a'b')'
- 杂技算法
#include<stdio.h>
#include<stdlib.h>
int gcd(int p,int q)
{
if(q == 0) return p;
return gcd(q,p%q);
}
void reverse(char arr[],int sz,int cnt)
{
int tmp,loopCnt = gcd(sz,cnt);
int i,j,k;
for(i=0;i<loopCnt;i++)
{
tmp = arr[i];
j = i;
while(1)
{
k = j + cnt;
if(k >= sz)
k = k - sz;
if(k == i)
break;
arr[j] = arr[k];
j = k ;
}
arr[j] = tmp;
}
}
int main(void)
{
char carr[]={'a','b','c','d','e','f','g','h'};
int sz = 8,i=0;
reverse(carr,sz,3);
printf("========\n");
for(i = 0 ;i < sz;i++)
{
printf("%c ",carr[i]);
}
printf("\n");
printf("========\n");
return 0;
}
比较
杂技算法的速度显然是求逆运算的两倍。杂技算法对数组中的每个元素仅仅存储和读取一次，而求逆算法需要两次。
思考
反转代码在文本编辑器中实现了行的移动
/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */
/* rotate.c -- time algorithms for rotating a vector
Input lines:
algnum numtests n rotdist
algnum:
1: reversal algorithm
2: juggling algorithm
22: juggling algorithm with mod rather than if
3: gcd algorithm
4: slide (don't rotate): baseline alg for timing
To test the algorithms, recompile and change main to call testrot
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXN 10000000
int x[MAXN];
int rotdist, n;
/* Alg 1: Rotate by reversal */
void reverse(int i, int j)
{ int t;
while (i < j) {
t = x[i]; x[i] = x[j]; x[j] = t;
i++;
j--;
}
}
void revrot(int rotdist, int n)
{ reverse(0, rotdist-1);
reverse(rotdist, n-1);
reverse(0, n-1);
}
/* Alg 2: Juggling (dolphin) rotation */
int gcd(int i, int j)
{ int t;
while (i != 0) {
if (j >= i)
j -= i;
else {
t = i; i = j; j = t;
}
}
return j;
}
void jugglerot(int rotdist, int n)
{ int cycles, i, j, k, t;
cycles = gcd(rotdist, n);
for (i = 0; i < cycles; i++) {
/* move i-th values of blocks */
t = x[i];
j = i;
for (;;) {
k = j + rotdist;
if (k >= n)
k -= n;
if (k == i)
break;
x[j] = x[k];
j = k;
}
x[j] = t;
}
}
void jugglerot2(int rotdist, int n)
{ int cycles, i, j, k, t;
cycles = gcd(rotdist, n);
for (i = 0; i < cycles; i++) {
/* move i-th values of blocks */
t = x[i];
j = i;
for (;;) {
/* Replace with mod below
k = j + rotdist;
if (k >= n)
k -= n;
*/
k = (j + rotdist) % n;
if (k == i)
break;
x[j] = x[k];
j = k;
}
x[j] = t;
}
}
/* Alg 3: Recursive rotate (using gcd structure) */
void swap(int i, int j, int k) /* swap x[i..i+k-1] with x[j..j+k-1] */
{ int t;
while (k-- > 0) {
t = x[i]; x[i] = x[j]; x[j] = t;
i++;
j++;
}
}
void gcdrot(int rotdist, int n)
{ int i, j, p;
if (rotdist == 0 || rotdist == n)
return;
i = p = rotdist;
j = n - p;
while (i != j) {
/* invariant:
x[0 ..p-i ] is in final position
x[p-i..p-1 ] = a (to be swapped with b)
x[p ..p+j-1] = b (to be swapped with a)
x[p+j..n-1 ] in final position
*/
if (i > j) {
swap(p-i, p, j);
i -= j;
} else {
swap(p-i, p+j-i, i);
j -= i;
}
}
swap(p-i, p, i);
}
int isogcd(int i, int j)
{ if (i == 0) return j;
if (j == 0) return i;
while (i != j) {
if (i > j)
i -= j;
else
j -= i;
}
return i;
}
void testgcd()
{
int i,j;
while (scanf("%d %d", &i, &j) != EOF)
printf("%d\n", isogcd(i,j) );
}
/* Test all algs */
void slide(int rotdist, int n) /* Benchmark: slide left rotdist (lose 0..rotdist-1) */
{ int i;
for (i = rotdist; i < n; i++)
x[i-rotdist] = x[i];
}
void initx()
{
int i;
for (i = 0; i < n; i++)
x[i] = i;
}
void printx()
{ int i;
for (i = 0; i < n; i++)
printf(" %d", x[i]);
printf("\n");
}
void roterror()
{
fprintf(stderr, " rotate bug %d %d\n", n, rotdist);
printx();
exit (1);
}
void checkrot()
{ int i;
for (i = 0; i < n-rotdist; i++)
if (x[i] != i+rotdist)
roterror();
for (i = 0; i < rotdist; i++)
if (x[n-rotdist+i] != i)
roterror();
}
void testrot()
{ for (n = 1; n <= 20; n++) {
printf(" testing n=%d\n", n);
for (rotdist = 0; rotdist <= n; rotdist++) {
/* printf(" testing rotdist=%d\n", rotdist); */
initx(); revrot(rotdist, n); checkrot();
initx(); jugglerot(rotdist, n); checkrot();
initx(); jugglerot2(rotdist, n); checkrot();
initx(); gcdrot(rotdist, n); checkrot();
}
}
}
/* Timing */
void timedriver()
{ int i, algnum, numtests, start, clicks;
while (scanf("%d %d %d %d", &algnum, &numtests, &n, &rotdist) != EOF) {
initx();
start = clock();
for (i = 0; i < numtests; i++) {
if (algnum == 1)
revrot(rotdist, n);
else if (algnum == 2)
jugglerot(rotdist, n);
else if (algnum == 22)
jugglerot2(rotdist, n);
else if (algnum == 3)
gcdrot(rotdist, n);
else if (algnum == 4)
slide(rotdist, n);
}
clicks = clock() - start;
printf("%d\t%d\t%d\t%d\t%d\t%g\n",
algnum, numtests, n, rotdist, clicks,
1e9*clicks/((float) CLOCKS_PER_SEC*n*numtests));
}
}
/* Main */
int main()
{ /* testrot(); */
timedriver();
return 0;
}
变位词程序的实现（边栏）
sign.c
#include<stdio.h>
#include<stdlib.h>
#define WORDMAX 100
int
charcmp (char *x, char *y)
{
return *x - *y;
}
int
main (void)
{
char word[WORDMAX], sig[WORDMAX];
while (scanf ("%s", word) != EOF)
{
strcpy (sig, word);
qsort (sig, strlen (sig), sizeof (char), charcmp);
printf ("%s %s\n", sig, word);
}
return 0;
}
squash.c
#include<stdio.h>
#include<stdlib.h>
#define WORDMAX 100
int
main (void)
{
char word[WORDMAX], oldsig[WORDMAX], sig[WORDMAX];
int linenum = 0;
strcpy (oldsig, "");
while (scanf ("%s %s", sig, word) != EOF)
{
if (strcmp (oldsig, sig) != 0 && linenum > 0)
printf ("\n");
strcpy (oldsig, sig);
linenum++;
printf ("%s ", word);
}
printf ("\n");
return 0;
}
sign < dic | sort | squash > gramlist 改命令将文件dic输入到程序，连接sign的输出至sort,连接sort的输出至squash,并将squash的输出写入文件gramlist。
运行结果：
[hadoop@Arch Pearls]$ gcc sign.c -o sign
[hadoop@Arch Pearls]$ gcc squash.c -o squash
[hadoop@Arch Pearls]$ sign < dic | sort | squash > gramlist
[hadoop@Arch Pearls]$ cat dic
pans
pots
opt
snap
stop
tops
[hadoop@Arch Pearls]$ cat gramlist
pans snap
pots stop tops
opt
一点说明:
- 关于解决问题，把程序化成一个个小块，每个小块实现一个小的功能，然后把各个功能块连接起来，组成一个大的应用。上面的程序就是一个很好的例子，
- sign.c负责生成单词的标识，并把生成的表示和单词输出。
- squash.c负责把临近的标识相同的单词按行放在同一行输出。
- 借助linux的sort命令把单词把标识单词相同的聚到一起。
- 关于qsort,快速排序，需要指定排序的方法,原型
void qsort(void*base,size_t num,size_t width,int(__cdecl*compare)(const void*,const void*));
[hadoop@Arch Pearls]$ a.out
age=10,height=180
age=10,height=190
age=18,height=180
[hadoop@Arch Pearls]$ cat qsort.c
#include<stdio.h>
struct Student
{
int age;
int height;
};
int
stucmp (struct Student *s1, struct Student *s2)
{
if (s1->age != s2->age)
return s1->age - s2->age;
else
return s1->height - s2->height;
}
int
main (void)
{
struct Student stu[3];
stu[0].age = 10, stu[0].height = 190;
stu[1].age = 18, stu[1].height = 180;
stu[2].age = 10, stu[2].height = 180;
qsort (stu, 3, sizeof (struct Student), stucmp);
int i = 0;
for (i = 0; i < 3; i++)
printf ("age=%d,height=%d\n", stu[i].age, stu[i].height);
return 0;
}
[hadoop@Arch Pearls]$ a.out
age=10,height=180
age=10,height=190
age=18,height=180
[hadoop@Arch Pearls]$
网友评论