筛素数更正

本文出自 写在之前 maker关于线性筛素数的论文。 做到欧拉线性筛法再做补充。(当时还写了个这?) 关于线性筛素数 之前一直没有正视线性筛素数的问题。今天特意来写一个伪证明。如果当前的i不是素数,那么必然被之前的某个素数筛掉了。i × prime[j]。 一个合数必然可以写成几个素数的乘积,再或者就是p×i这种形式。如果能被i×p1筛掉之后则不需要i×p2继续筛了,i×p2可以写成p1×(i×p2) 例如12可以被6×2筛掉,之前4×3这种筛除就可以去掉。 这种方法会不会存在没有筛掉的合数? 不可能:i会一直到n,也就是整个范围都会包含在内。 代码: memset(Prime, , sizeof(Prime)); memset(IsPrime, 1, sizeof(IsPrime)); for(i = 2 ; i <= n; i++) { if(IsPrime[i]) Prime[num++] = i; for(j = ; j < num && i * Prime[j] <= n; j++) { IsPrime[i * Prime[j]] = ; if(i % Prime[j] == ) break; } } 之前的错误在于筛素数的时候没有筛去2的倍数,所以出现后面的值错误。

Read More

线性时间选择

定义 在给定线性序集中n个元素和一个整数k,要求找出n个元素中第k小的数。 方法一 线性时间选择,可以使用堆排序,这样就可以在$O(n+klog_n)=O(n)_的时间内找到的k小的元素。 方法二 使用快速排序中的分块算法,对所需要选择的数组分块,分完以后再在剩余的部分中,寻找(k – 减去分块的大小) 代码如下: template <class Type> int Partition(Type a[], int p, int r) { int i = p; j = r+1; Type x = a[p]; while(1) { while(a[++i] < x); while(a[--j] > x); if(i >= j) break; swap(a[i], a[j]); } a[p] = a[j]; a[j] = x; return j; } template <class Type> int RandomPartition(Type a[], int p, int r) { int i = Random(p, r); swap(a[i], a[p]); return Partition(a, p, r); } template <class Type> Type RandomizedSelect(Type a[], int p, int r, int k) { if(p == r) return a[p]; int i = RandomPartition(a, p, r); j = i - p + 1; // 分块的大小 if(k <= j) return RandomizedSelect(a, p, i, k); else return RandomizedSelect(a, i+1, r, k-j); } 但是此方法在最差的情况下需要$n^2$的时间,比如在寻找最小元素时,总是在最大的元素划分。

Read More

给小白的IPython Notebook指南

这是给“小白”的notebook指南。notebook是算法开发经常使用的工具。 安装notebook $ pip install notebook 运行notebook $ jupyter-notebook . 在终端下运行这个命令可以启动notebook。 使用IPython-Notebook 点击右方的New按钮,选择Python3,以此来启动一个新的NoteBook。 这时会新创建一个文件。 在In [ ]:后输入要运行的代码,然后点击Run即可运行。例如: 使用Terminal Terminal就是之前在Windows下的cmd,MacOS下的terminal,点击之后见到这个界面: 尝试输入python,就可以像之前那样进行命令行编程了。

Read More

网络-CDMA接受检验

{% blockquote 本文出自 http://svtter.com svtter.com %} 本文可以随意转载,但是转载请保留本信息. 做CDMA简单的接收处理。 文件 input: -1 -1 -1 1 1 -1 1 1 -1 -1 1 -1 1 1 1 -1 -1 1 -1 1 1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 new.c: #include <stdio.h> #include <math.h> #define M 8 const int b[] = {-1, 1, -3, 1, -1, -3, 1, 1}; void show(int a[]) { int i; for(i = ; i < M; i++) printf("

Read More

获取本机ipv6地址

获取本机ipv6地址,最简单的方法: cat /proc/net/if_inet6 还可以使用python的netinterface包。 ifconfig也是从这个文件进行获取的,只是优化了一下格式。 reference https://blog.lilydjwg.me/2012/6/6/get-ipv4-and-ipv6-addresses-of-local-host-in-a-programming-way.34055.html

Read More

蓝桥杯入门训练题目

蓝桥的系统需要I64d这种输入格式。无力吐槽。 Fibonacci数列 #include <iostream> #include <cstdio> #include <cstring> #include <set> #include <vector> #include <map> #include <algorithm> #include <queue> #include <cmath> #include <bitset> using namespace std; // 大数,内存处理 #define INF 0x3f3f3f3f #define lln long long int #define MEM(a) memset(a, 0, sizeof(a)) #define MEMM(a) memset(b, -1, sizeof(b)) #define DEB(x, n) cout << (x) << " " << (n) << endl #define CR printf("\n") // 调试用 template <class Type> void debug(Type a[], int len) { for(int i = ; i < len ; i++) { cout << a[i] << "

Read More

蓝桥杯基础练习

数列排序 #include <iostream> #include <cstdio> #include <cstring> #include <set> #include <vector> #include <map> #include <algorithm> #include <queue> #include <cmath> #include <bitset> using namespace std; // 大数,内存处理 #define INF 0x3f3f3f3f #define lln long long #define MEM(a) memset(a, 0, sizeof(a)) #define MEMM(a) memset(b, -1, sizeof(b)) #define DEB(x, n) cout << (x) << " " << (n) << endl #define CR printf("\n") // 调试用 template <class Type> void debug(Type a[], int len) { for(int i = ; i < len ; i++) { cout << a[i] << "

Read More