NOIP考前复习-数制转换,数论模板与文件读写

数制转换有两种题型,一般一题,分值1.5分。

题型一R进制转十进制

解法就是:按权展开,但要注意各个位的权,最低位(最右边)的权是0次方,权值为1。

纯整数的情况:

(11010110)= 1×27 + 1×26 + 0×25 + 1×24 + 0×23 + 1×22 + 1×21 + 0×2 =  (214)10

(2365)8 = 2×83 + 3×82 + 6×81 + 5×8=  (1269)10

(4BF)16 = 4×162 + B×161 + F×16=  (1215)10

整数带小数的情况:

(110.011)= 1×22 + 1×21 + 0×20 + 0×2-1 + 1×2-2 + 1×2-3 =  (6.375)10

(5.76)8 = 5×80 + 7×8-1 + 6×8-2 =  (5.96875)10

(D.1C)16 = D×160 + 1×16-1 + C×16-2  = (13.109375)10

题型二十进制转R进制

注意:十进制的小数转R进制未必可以转完。


 每日练习

一、任意进制转十进制

1、(1101101)2      = (           )

2、(7754)8       = (           )

3、(F1B9AC)16   = (           )

4、(1011.11101)2   = (           )

5、(75.1076)8     = (           )

6、(59D.10AC)16  = (           )

二、十进制转任意进制

1、(173)10     = (          )2

2、(173.125)10 = (          )2

3、(173)10     = (          )8

4、(173.625)10 = (          )8

5、(173)10     = (          )16

6、(173.375)10 = (          )16


 往年真题

1. 与16进制数 A1.2等值的10进制数是(  )

A.101.2      B.111.4        C.161.125     D.177.25

2. 2E+03表示(  )

A.2.03      B.5        C.8     D.2000

3. 在字长为16位的系统环境下,一个16位带符号整数的二进制补码为1111111111101101。其对应的十进制整数应该是(   )

A.19          B.-19          C.18        D.-18

4. 十进制小数125.125对应的八进制数是(   )

A.100.1       B.175.175     C.175.1     D.100.175

5. 与十进制数28.5625相等的四进制数是(  )

A.123.21       B.131.22        C.130.22      D.130.21     E.130.20

6.  (2008)10+  (5B)16 的结果是(   )。

A.(833)16          B.(2099)10       C.(4063)8      D.(100001100011)2

7. 与十进制数28.5625相等的四进制数是(  )。

A. 123.21       B. 131.22        C. 130.22       D. 130.21

8.  (2008)10+ (5B)16的结果是(   )。

A. (833)16       B. (2089)10       C. (4163)8       D. (100001100011)2

9. 算式 (1000)10-(100)16-(10)8的结果是(   )。

A. (890)10     B. (986)8       C. (1011100000)2       D. (2E0)16        E. (736)10

10. 与十进制数17.5625相对应的8进制数是(   )

A. 21.5625     B. 21.44     C. 21.73      D. 21.731      E. 前4个答案都不对

11.  (2070)16+(34)8的结果是(   ).

A. (8332)10      B. (208C)16     C. (100000000110)2     D. (20214)8

题解:统一为二进制运算,然后再转其他进制

12. 与十进制数1770对应的八进制数是(  )。

A.3350           B.3351             C.3352             D.3540

13.  (2070)16 + (34)8 的结果是(   )。

A.(8332)10   B.(208A)16   C.(100000000110)2     D.(20212)8

14. 与十进制数1770.625对应的八进制数是(  )。

A. 3352.5       B. 3350.5      C. 3352.1161

D. 3350.1151    E. 前4个答案都不对

15. (2010)16 + (32)8的结果是(  )。

A. (8234)10    B. (202A)16     C. (100000000110)2  D. (2042)16


真题参考答案:

1A 2BC 3B 4A 5A 6B 7AC

8AD 9D 10C 11E 12AC 13A 14A

文件读入读出

假设题目名为“add”,那么文件夹名为“add”,c++程序名为“add.cpp”,读入文件名为“add.in”,输出文件名为“add.out”。四个的拼写均不可有误,包括大小写差异。千万不要调试后就忘记修改文件读入读出了。

#include<cstdio>

int main(){

freopen("add.in","r",stdin);//read

freopen("add.out","w",stdout);//write

}


数论算法

1、线性筛

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

using namespace std;

const int maxn=200005;

int prime[maxn];

bool not_prime[maxn];

int main()

{

int n,cnt=0;

scanf("%d",&n);

memset(not_prime,0,sizeof(not_prime));

not_prime[1]=true;

for(inti=2;i<=n;i++)

{

if(!not_prime[i])

prime[++cnt]=i;

for(intj=1;j<=cnt;j++)

{

if(prime[j]*i>n)    break;

not_prime[prime[j]*i]=true;

if(i%prime[j]==0) break;

}

}

for(inti=1;i<=cnt;i++)

printf("%d ",prime[i]);

return 0;

}

2、埃氏筛

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

using namespace std;

inline int read()

{

char c;

c=getchar();

for(;c>'9'||c<'0';c=getchar());

int sum=0;

for(;c<='9'&&c>='0';c=getchar())sum=sum*10+c-48;

return sum;

}

int n,m;

bool f[10010000];

int main()

{

n=read(),m=read();

memset(f,true,sizeof(f));

f[0]=f[1]=false;

for(inti=2;i<=n;i++)

if(f[i])

for(intj=2;i*j<=n;f[i*j]=false,j++);

for(inti=1;i<=m;i++)

{

int x;

x=read();

if(f[x])printf("Yes\n");

elseprintf("No\n");

}

return 0;

}

3、拓展欧几里得算法

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

using namespace std;

int x,y;

int exgcd(int a,int b)

{

if(!b)

{

x=1;

y=0;

return a;

}

else

{

int t;

intd=exgcd(b,a%b);

t=x;

x=y;

y=t-a/b*x;

return d;

}

}

int main()

{

int a,b;

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

exgcd(a,b);

// cout<<__gcd(a,b)<<endl;

cout<<x<<" "<<y<<endl;

return 0;

}

4、GCD&LCM(求最小公倍数与最大公约数) 暂时代码是转载的

#include<iostream>

#include<cstdio>

#include<cstdlib>

using namespace std;

int gcd(int a,int b)

{

if(!b) returna;

else returngcd(b,a%b);

}

int lcm(int a,int b)

{

returna/gcd(a,b)*b;

}

int main()

{

int a,b;

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

cout<<gcd(a,b)<<" "<<lcm(a,b)<<endl;

return 0;

}

5、分解质因数

#include<iostream>

#include<cstdio>

#include<cstdlib>

using namespace std;

int main()

{

long long n;

scanf("%lld",&n);

for(long longi=2;i<=n;i++)

{

while(n!=i)

{

if(n%i==0)

{

printf("%lld*",i);

n=n/i;

}

elsebreak;

}

}

printf("%lld",n);

return 0;

}

6、大数翻倍法

#include<iostream>

#include<cstdio>

#include<cstdlib>

using namespace std;

int a[233],mo[233];

int gcd(int a,int b)

{

if(!b) returna;

else returngcd(b,a%b);

}

int lcm(int a,int b)

{

returna/gcd(a,b)*b;

}

int main()

{

int n;

scanf("%d",&n);

for(inti=1;i<=n;i++)

scanf("%d%d",&a[i],&mo[i]);

intans=0,nowmo=1;

for(inti=1;i<=n;i++)

{

intother=a[i],othermo=mo[i];

if(othermo>nowmo)

{

swap(ans,other);

swap(nowmo,othermo);

}

while(ans%othermo!=other)

ans+=nowmo;

nowmo=lcm(nowmo,othermo);

}

printf("%d",ans);

}

7、快速幂

#include<bits/stdc++.h>

using namespace std;

const int MOD = 1007;

int xx(int a,int n,int MOD)

{

int ret=1;

int tmp=a%MOD;

while(n)

{

if(n&1)

ret=ret*tmp%MOD;

tmp=tmp*tmp%MOD;

n>>=1;

}

return ret;

}

int main()

{

int m,n;

while(scanf("%d%d",&m,&n)==2)

{

printf("%d\n",xx(m,n,MOD));

}

}

8、位运算

功能

示例

位运算

去掉最后一位

(101101->10110)

x >> 1

在最后加一个0

(101101->1011010)

x  << 1

在最后加一个1

(101101->1011011)

x << 1+1

把最后一位变成1

(101100->101101)

x  | 1

把最后一位变成0

(101101->101100)

x | 1-1

最后一位取反

(101101->101100)

x  ^ 1

把右数第k位变成1

(101001->101101,k=3)

x | (1 << (k-1))

把右数第k位变成0

(101101->101001,k=3)

x  & !(1 << (k-1))

右数第k位取反

(101001->101101,k=3)

x ^ (1 << (k-1))

取末三位

(1101101->101)

x  & 7

取末k位

(1101101->1101,k=5)

x & (1<< k -1)

取右数第k位

(1101101->1,k=4)

x  >> (k-1) & 1

把末k位变成1

(101001->101111,k=4)

x | (1 << k-1)

末k位取反

(101001->100110,k=4)

x  ^ (1 << k-1)

把右边连续的1变成0

(100101111->100100000)

x & (x+1)

把右起第一个0变成1

(100101111->100111111)

x  | (x+1)

把右边连续的0变成1

(11011000->11011111)

x | (x-1)

取右边连续的1

(100101111->1111)

(x  ^ (x+1)) >> 1

去掉右起第一个1的左边

(100101000->1000)

x & (x ^ (x-1))

上一篇:2019-04-11-day030-网络编程并发


下一篇:nodejs开发环境sublime配置