编程珠玑的一些笔记

川长思鸟来 2022-07-16 13:17 334阅读 0赞

**位操作****:** **关于除法****,** **取模**

i >> SHIFT <=> i/32

i&MASK <=> i%32 \[大于32的部分(是32的倍数)都被与掉\]

\#defineN 10000000

\#defineSHIFT 5

\#defineMASK 0x1f

\#defineBITSPERWORD 32

inta\[N/BITSPERWORD\+1\];

voidset\_bit(int i)

a\[i>>SHIFT\] |= 1<<(i&MASK);

voidclr\_bit(int i)

a\[i>>SHIFT\] &= ~(1<<(i&MASK));

inttest\_bit(int i)

return a\[i>>SHIFT\] & (1<<(i&MASK));

**随机数的产生的相关内容**

\#include<iostream>

\#include<time.h>

\#include<stdlib.h>

\#include<algorithm>

usingnamespace std;

inlinevoid exchange(int \*arr, int i, int j)

int temp = arr\[i\];

arr\[i\] = arr\[j\];

arr\[j\] = temp;

//一般的rand()产生2^15次方的数量级

//产生一个较大的随机数(到2^30数量级)

intbigrand()

return (RAND\_MAX)\*rand()+rand();

//产生一个在区间\[l, h\]之间的随机数

intrandint(int l, int h)

return l\+bigrand()%(h\-l\+1);

//产生m个在\[0,n-1\]之间的有序的随机数

//Knuth法:

//时间O(n), 空间O(1)

voidrandsortedint\_knuth(int m, int n)

for (int i = 0; i < n; i\++)

if(bigrand() % (n\-i) < m)

cout << i << "/n";

m\--;

//产生m个在\[0, n-1\]之间的有序的随机数

//弄乱数组法:

//时间O(m\*logm), 空间O(n)

voidrandsortedint\_shuffer(int m, int n)

int \*arr = new int\[n\];

for(int i = 0; i < n; ++i)

arr\[i\] = i;

for(int i = 0; i < m; ++i)

exchange(arr, i, randint(i, n\-1));

sort(arr, arr\+m);

for(int i = 0; i < m; ++i)

cout << arr\[i\] << endl;

//产生m个在\[0,n-1\]之间的有序的随机数

//floyd法:

//时间:O(m\*logm), 空间O(m)

voidrandsortedint\_floyd(int m, int n)

set<int> s;

for(int i = n\-m; i < n; i\++)

int t = bigrand()%(i\+1);

if(s.find(t) == s.end())

s.insert(t);

else

s.insert(i);

for(set<int>::iterator i = s.begin(); i != s.end(); ++i)

cout << \*i << endl;

intmain()

srand(unsigned(time(NULL)));

return 0;

**旋转一个向量**

**如****: abcdefg -> defgabc**

1. 置换法

voidjuggle\_rotate(int rotate\_dist, int n)

int cycles = gcd(rotate\_dist, n);

for (int i = 0; i < cycles; ++i)

int current = i;

int offset;

int temp = x\[i\];

for(;;)

offset = (current \+ rotdist) % n;

if(offset == i)

break;

x\[current\] = x\[offset\];

current = offset;

x\[current\] = temp;

printArray();

//递归实现

void\_rotate\_cur(char\* arr, int beg, int end, int i)

if(i\-beg < end\-i\+1)

int cnt = i\-beg;

for(int j = 0; j < cnt; ++j)

int temp = arr\[beg\+j\];

arr\[beg\+j\] = arr\[end\-cnt\+1+j\];

arr\[end\-cnt\+1+j\] = temp;

\_rotate\_cur(arr, beg, end\-cnt, i);

else if(i\-beg > end\-i\+1)

int cnt = end\-i\+1;

for(int j = 0; j < cnt; ++j)

int temp = arr\[beg\+j\];

arr\[beg\+j\] = arr\[i\+j\];

arr\[i\+j\] = temp;

\_rotate\_cur(arr, beg\+cnt, end, i);

else

int cnt = i\-beg;

for(int j = 0; j < cnt; ++j)

int temp = arr\[beg\+j\];

arr\[beg\+j\] = arr\[i\+j\];

arr\[i\+j\] = temp;

void\_rotate(char\* arr, int n, int i)

\_rotate\_cur(arr, 0, n\-1, i);

//迭代实现

voidswap(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\++;

voidgcdrot(int rotdist, int n)

int i, j, p;

if (rotdist == 0 || rotdist == n)

return;

i = p = rotdist;

j = n \- p;

while (i != j) \{

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);

**寻找第一次出现的某个元素的二分查找法**

\#include<iostream>

usingnamespace std;

intsearch1(int\* x, int n, int t)

int l = -1, u = n;

while (l\+1 != u)

int m = (l\+u) >> 1;

if (x\[m\] < t)

l = m;

else

u = m;

int p = u;

if(p >= n || x\[p\] != t)

p = -1;

return p;

intsearch2(int\* x, int n, int t)

int low = 0, high = n\-1;

int p = -1;

while (low <= high)

int mid = (low\+high)>>1;

if(x\[mid\] == t)

p = mid;

high = mid\-1;

else if(t > x\[mid\])

low = mid\+1;

else

high = mid\-1;

return p;

intmain()

int arr\[\] = \{1,2,2,2,2,4,5,6,6\};

cout << search1(arr, 9, 2) << endl;

cout << search2(arr, 9, 6) << endl;

return 0;

**快速排序****, Shell****排序**

\#include<iostream>

\#include<time.h>

\#include<stdlib.h>

\#defineN 1000

usingnamespace std;

inlinevoid exchange(int \*arr, int i, int j)

if(i == j)

return;

int temp = arr\[i\];

arr\[i\] = arr\[j\];

arr\[j\] = temp;

voidprint\_array(int \*arr, int n)

for(int i = 0; i < n; ++i)

printf("%d ", arr\[i\]);

printf("/n");

intpartition1(int \*arr, int l, int h)

int j = l;

for(int p = l\+1; p <= h; ++p)

if(arr\[p\] < arr\[l\])

exchange(arr, p, ++j);

exchange(arr, l, j);

return j;

intpartition2(int \*arr, int l, int h)

int i = l\+1, j = h;

while (1)

while (i <= h && arr\[i\] < arr\[l\])

i\++;

while (arr\[j\] > arr\[l\])

j\--;

if(i > j)

break;

exchange(arr, i\++, j\--);

exchange(arr, l, j);

return j;

//add atferwards 2010-08-01

intpartition3(int \*arr, int l, int h)

int i = l, j = h;

int temp = arr\[l\];

while (i < j)

while(i < j && arr\[j\] >= temp)

j--;

arr\[i\] = arr\[j\];

while(i < j && arr\[i\] <= temp)

i++;

arr\[j\] = arr\[i\];

arr\[i\] = temp;

return j;

voidquick\_sort1(int \*arr, int l, int h)

if(l < h)

int p = partition1(arr, l, h);

quick\_sort1(arr, l, p\-1);

quick\_sort1(arr, p\+1, h);

voidquick\_sort2(int \*arr, int l, int h)

if(l < h)

int p = partition2(arr, l, h);

quick\_sort2(arr, l, p\-1);

quick\_sort2(arr, p\+1, h);

voidshell\_sort(int \*arr, int n)

int h;

for(h = 1; h < n; h = 3\*h \+ 1)

;

for(h /= 3; h >= 1; h /= 3)

for(int i = h; i < n; ++i)

for(int j = i; j >= h; j \-= h)

if(arr\[j\-h\] > arr\[j\])

exchange(arr, j, j\-h);

else

break;

//寻找第k大的元素

voidfind\_kth(int \*arr, int l, int h, int k)

if (l < h)

int p = partition1(arr, l, h);

if(k < p)

find\_kth(arr, l, p\-1, k);

else if(k > p)

find\_kth(arr, p\+1, h, k);

编程珠玑的一些笔记

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关编程珠玑笔记 ~~ 性能部分

相关 [Unix]shell编程珠玑（5）

相关【编程珠玑】第十五章字符串

相关编程珠玑中的问题(1)——向量旋转

相关编程珠玑中一些算法

相关编程珠玑的一些笔记

相关编程珠玑：位向量

相关编程珠玑笔记~~开篇

相关《编程珠玑》读书笔记(2,3)

相关编程珠玑 ~~ 啊哈! 算法