当前位置：文档库 › 无限序列 C语言实现

无限序列 C语言实现

【问题描述】

我们按以下方式产生序列：

1、开始时序列是： "1" ；

2、每一次变化把序列中的 "1" 变成 "10" ，"0" 变成 "1"。

经过无限次变化，我们得到序列"1011010110110101101..."。

总共有 Q 个询问，每次询问为：在区间A 和B 之间有多少个 1。

任务写一个程序回答Q 个询问

输入第一行为一个整数 Q，后面有Q 行，每行两个数用空格隔开的整数 a, b。

输出共Q 行，每行一个回答

约定

1 <= Q <= 5000

1 <= a <= b < 263

样例

infinit.in infinit.out

1 4

2 8

分析：

我们先看看序列变化规律，S1 = "1", S2 = "10", S3 = "101", S4 = "10110", S5 =

"10110101", 等等 . Si 是 S （i+1）的前缀。序列 Si 是由序列 S （i-1）和 S （i-2）, 连接而成的。

即 Si = Si-1 + Si-2 (实际上上是 Fibonacci数列)。

找到规律以后，我们可以可以用递归的方法求出从从位置 1到位置 X之间所有的 1的个数，用一

个函数 F计算，结果为 f(b)-f(a-1)。

时间复杂度为： O(Q * log MAX_VAL)

此题需要先找出数学规律，再进用递归实现。主要考查选手的数学思维能力和递归程序的实现。

#include

using namespace std;

unsigned long long int see(unsigned long long int n)

{

unsigned long long int a1=1,a2=2,b1=1,b2=1;

if(n==1||n==2)return 1;

while(a2

{

unsigned long long int t;

t=a2;

a2=a2+a1;//printf("%d\n",a2);

a1=t;

t=b2;

b2=b2+b1;

b1=t;

}

if(a2==n)

return b2;

unsigned long long int f=n-a1;

b1=b1+see(f);

return b1;

}

int main()

{

int t;

unsigned long long int a,b;

scanf("%d",&t);

while(t--)

{

scanf("%I64u%I64u",&a,&b);

{

unsigned long long int sum;

if(a!=1)

sum=see(b)-see(a-1);

else

sum=see(b);

printf("%I64u\n",sum); }

}

return 0;

}

RSA加密算法_源代码__C语言实现

RSA算法 1978年就出现了这种算法，它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, AdiShamir 和Leonard Adleman。但RSA的安全性一直未能得到理论上的证明。 RSA的安全性依赖于大数难于分解这一特点。公钥和私钥都是两个大素数（大于100个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。密钥对的产生。选择两个大素数，p 和q 。计算：n = p * q 然后随机选择加密密钥e，要求e 和( p - 1 ) * ( q - 1 )互质。最后，利用Euclid 算法计算解密密钥d, 满足e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )其中n和d也要互质。数e和n是公钥，d是私钥。两个素数p和q 不再需要，应该丢弃，不要让任何人知道。加密信息m（二进制表示）时，首先把m分成等长数据块m1 ,m2,..., mi ，块长s，其中2^s <= n, s 尽可能的大。对应的密文是：ci = mi^e ( mod n ) ( a ) 解密时作如下计算：mi = ci^d ( mod n ) ( b ) RSA 可用于数字签名，方案是用( a ) 式签名，( b )式验证。具体操作时考虑到安全性和m信息量较大等因素，一般是先作HASH 运算。RSA 的安全性。RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA 就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解140多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定。由于进行的都是大数计算，使得RSA最快的情况也比DES慢上100倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。 */ #include #include #include using namespace std;//RSA算法所需参数 typedef struct RSA_PARAM_Tag { unsigned __int64 p, q; //两个素数，不参与加密解密运算 unsigned __int64 f; //f=(p-1)*(q-1)，不参与加密解密运算 unsigned __int64 n, e; //公匙，n=p*q，gcd(e,f)=1 unsigned __int64 d; //私匙，e*d=1 (mod f)，gcd(n,d)=1 unsigned __int64 s; //块长，满足2^s<=n的最大的s，即log2(n) } RSA_PARAM;//小素数表 const static long g_PrimeTable[]= { 3, 5, 7, 11, 13, 17, 19, 23,

大一上期C语言实验报告5 循环控制语句

成都工业学院·计算机工程学院《程序设计基础》实验报告 1.实验目的（1）熟练掌握while语句、do…while语句和for语句格式及使用方法，掌握三种循环控制语句的循环过程以及循环结构的嵌套，利用三种循环语句实现循环结构；（2）掌握简单、常用的算法，并在编程过程中体验各种算法的编程技巧；（3）进一步学习调试程序，掌握语法错误和逻辑错误的检查方法。2.实验内容（1）输出两个整数m和n，求它们的最大公约数和最小公倍数。要求： ①画出算法流程图，从键盘输入m和n； ②对负数和零可不做考虑； ③运行程序，对m>n、m

③按照数字、大写字母、小写字母及其他字符数的顺序输出结果 3.流程图 4.源程序

5. 运行结果（1 ）求最大公约数和最小公倍数（2）求1000内最大的10个素数之和（3）计算π值

RC4加密算法C语言实现

RC4 加密算法 C 语言实现代码文件名 RC4.cpp Encrypt.h (代码详见后文) 备注：将以上两个文件放在相同的路径(建议不要放在中文路径下)编译执行！编译环境 Microsoft Visual C++ 6.0 C-Free 5.0 代码解释 RC4 加密算法是大名鼎鼎的RSA 三人组中的头号人物Ron Rivest 在1987 年设计的密钥长度可变的流加密算法簇。之所以称其为簇，是由于其核心部分的S-box 长度可为任意，但一般为256字节。该算法的速度可以达到DES 加密的10倍左右。 RC4 算法的原理很简单，包括初始化算法和伪随机子密码生成算法两大部分。假设S-box 长度和密钥长度均为为n。先来看看算法的初始化部分(用类C伪代码表示)： for (i=0; i

} 得到的子密码sub_k用以和明文进行xor运算，得到密文，解密过程也完全相同。 RC4加密算法在C++中的实现： RC4函数(加密/解密)：其实RC4只有加密，将密文再加密一次，就是解密了。 GetKey函数：随机字符串产生器。 ByteToHex函数：把字节码转为十六进制码，一个字节两个十六进制。十六进制字符串非常适合在HTTP中传输。 HexToByte函数：把十六进制字符串，转为字节码。。 Encrypt函数：把字符串经RC4加密后，再把密文转为十六进制字符串返回，可直接用于传输。 Decrypt函数：直接密码十六进制字符串密文，再解密，返回字符串明文。源代码以下为Encrypt.h文件代码 #ifndef _ENCRYPT_RC4_ #defi ne _ENCRYPT_RC4_ #in clude #defi ne BOX_LEN 256 int GetKey(c onst un sig ned char* pass, int pass_le n, un sig ned char *out); int RC4(c onst un sig ned char* data, int data_le n, const un sig ned char* key, int key_le n, un sig ned char* out, i nt* out_le n); static void swap_byte( un sig ned char* a, un sig ned char* b); char* En crypt(co nst char* szSource, const char* szPassWord); // 加密，返回加密结果 char* Decrypt(co nst char* szSource, con st char* szPassWord); // 解密，返回解密结果 char* ByteToHex(c onst un sig ned char* vByte, const int vLe n); // 把字节码pbBuffer转为十六进制字符串，方便传输 unsigned char* HexToByte(const char* szHex); // 把十六进制字符串转为字节码pbBuffer，解码 #e ndif // #ifndef _ENCRYPT_RC4_

c语言循环语句和循环控制例题解析

一、循环控制 (一)、break语句 break语句通常用在循环语句和开关语句中。当break用于开关语句switch中时，可使程序跳出switch而执行switch以后的语句；如果没有break语句，则将成为一个死循环而无法退出。break在switch中的用法已在前面介绍开关语句时的例子中碰到，这里不再举例。当break语句用于do-while、for、while循环语句中时，可使程序终止循环而执行循环后面的语句，通常break语句总是与if语句联在一起。即满足条件时便跳出循环。例如： int main(int argc, char *argv[]) { int sn=0,i; for(i=1;i<=100;i++) { if(i==51) break; /*如果i等于51，则跳出循环*/ sn+=i; /*1+2+……+50*/ } printf(%d\n,sn); } 可以看出，最终的结果是1+2+……+50。因为在i等于51的时候，就跳出循环了。自己写写怎样在while和do--while循环中增加break语句。注意: 1. break语句对if-else的条件语句不起作用。 2. 在多层循环中，一个break语句只向外跳一层。例如： int main(int argc, char *argv[]) { int i,j; printf(i j\n); for(i=0;i<2;i++) for(j=0;j<3;j++) { if(j==2) break; printf(%d %d\n,i,j); } } 输出结果为: i j 0 0 0 1 1 0 1 1 当i==0,j==2时，执行break语句，跳出到外层的循环，i变为1。 (二)、continue语句