C/C++ 数制专题

数制专题

2893.数据密度

所有类型的数据在内存中都是以二进制的形式存放的。其中有些位是 1，而有些位是 0。例如：字符 A 的二进制表示 01000001 中有 2 位是 1，6 位是 0。设 sizeof(char) 为 1。
数据密度定义为一块内存数据中 1 的位的占比。
写程序计算一组字符的数据密度。
对于每一行中的一组字符，以最简分数形式在一行中输出其数据密度。
分数格式：分子 / 分母

#include <iostream>
#include <string>
using namespace std;int gcd(int a, int b)
{return a ? gcd(b % a, a) : b;
}int main()
{int t; cin >> t;getchar();for (int i = 0; i < t; i++){string s; getline(cin, s);//char s[130]; //cout <<"**"<< s<<"**" << endl;//counts 1int cnt = 0;//int len = strlen(s);int len = s.length();for (int j = 0; j < len; j++){unsigned char c = s[j];for (int m = 0; m < 8; m++){cnt += c % 2;c >>= 1;}}int g = gcd(cnt, len * 8);cout << cnt / g << "/" << len * 8 / g << endl;}
}

3053.神秘信息

未来的某一天，人类登陆火星。在火星上发现一组由各种符号表示的神秘信息。研究发现：每种符号表示一个数码，神秘信息是一个整数。但是不知道每个符号表示的是哪个数码，也不知道它是几进制数 (只知道不可能是一进制)，但知道相同的符号表示相同的数码，不同的符号表示不同的数码。

符号总计有 62 种，为方便起见，每种符号分别用大小写英文字母和数字 0-9 表示。

现在我们想要知道神秘信息表示的最小整数值。

例如 :

11001001 最小整数值和人类的二进制数一样，为 201；

cats 最小整数值为 75(设是 4 进制数，c 表示 1，a 表示 0，t 表示 2，s 表示 3)；

pig 最小整数值为 11(设是 3 进制数，p 表示 1，i 表示 0，g 表示 2)。

注意：神秘信息表示的数必须是有意义的，第一位不能为 0。

#include <iostream>
#include <cstdio>
using namespace std;void solve()
{char s[61]; cin >> s;int num[128];for (int i = 0; i < 128; i++) num[i] = -1;int cnt = 0;char* p = s;num[*p] = 1;//首位表示1while (*++p){if (num[*p] == -1){num[*p] = cnt;cnt = cnt ? cnt + 1 : 2;}}if (cnt < 2) cnt = 2;//不可能1进制long long ans = 0;p = s;while (*p) ans = ans * cnt + num[*p++];printf("%lld\n", ans);
}int main()
{int t; cin >> t;for (int i = 0; i < t; i++){cout << "case #" << i << ":" << endl;solve();}
}

3190.平衡三进制

#include <iostream>
#include <math.h>using namespace std;int main()
{int t; cin >> t;for (int i = 0; i < t; i++){string num; cin >> num;int len = num.size();double ans = 0;int cnt = 0;//num.erase(num.size() - 1, 1);while (len!=0){if (num[len - 1] == '1') ans += pow(3, cnt);if (num[len - 1] == '-') ans -= pow(3, cnt);cnt++;num.erase(len - 1, 1);len--;//cout << "num:" << num << " ans:" << ans << endl;}cout << "case #" << i << ":" << endl;cout << ans << endl;}
}

1147.进制转换

输入一个十进制数N，将它转换成R进制数输出。

#include <stdio.h>
#include <stdlib.h>void trans(int x,int r)
{int a[100],cnt=0;while(x!=0){a[cnt]=(x%r);cnt++;x/=r;}for(int i=cnt-1;i>=0;i--){if(a[i]>=10)printf("%c",(a[i]-10+'A'));else printf("%d",a[i]);}
}int main()
{int t;scanf("%d",&t);getchar();for(int i=0;i<t;i++){int n;scanf("%d",&n);getchar();int r;scanf("%d",&r);if(n<0){int temp=-n;printf("-");trans(temp,r);}else if(n==0) printf("0");else trans(n,r);printf("\n");}return 0;
}

3037.十六进制加法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>void rev(char ch1[])//nixu ch1
{int len=strlen(ch1);int time=len/2,i,temp;for(i=0;i<time;i++){temp=ch1[i];ch1[i]=ch1[len-1-i];ch1[len-1-i]=temp;}
}int big(int a,int b)
{if(a>b) return a;else return b;
}int ctoi(char a)//char>>int
{int x=a-'0',y=a+10-'A';if(a=='\0') return 0;else if(a<='9') return x;else return y;
}char itoc(int a)//int>>char
{char x=a+'0',y=a-10+'A';if(a<=9) return x;else return y;
}int main()
{//printf("%c %d",itoc(16),ctoi('F'));int t;scanf("%d",&t);for(int i=0;i<t;i++){char n[201]={'\0'},m[201]={'\0'};char sum[205]={'\0'};int ci=0;scanf("%s %s",n,m);rev(n);rev(m);int len1=strlen(n),len2=strlen(m);int len=big(len1,len2);for(int j=0;j<len;j++){int a=ctoi(n[j]);int b=ctoi(m[j]);int s=a+b+ci;if(s>=16){sum[j]=itoc(s-16);ci=1;}else{sum[j]=itoc(s);ci=0;}if(j==len-1&&ci==1) sum[len]='1';}printf("case #%d:\n",i);rev(sum);printf("%s\n",sum);}return 0;
}

2876.二进制位不同的个数

#include <stdio.h>
#include <stdlib.h>int main()
{int t;scanf("%d",&t);for(int i=0;i<t;i++){int a,b,a1[1000]={0},b1[1000]={0};scanf("%d %d",&a,&b);int cnt=0,c=a^b;while(c!=0){cnt+=c%2;c=c>>1;}printf("%d\n",cnt);}return 0;
}

3040.非重复二进制串

对于一个二进制串 b=bkbk-1…b1，如果对任意 i (1≤i≤k-1)，满足 bi≠bi+1，那么 b 称为非重复二进制串。给定一个正整数，输出其二进制表示中最长的非重复二进制串的长度。

#include <stdio.h>
#include <stdlib.h>int main()
{int t;scanf("%d",&t);for(int i=0;i<t;i++){int n,cnt=0,a[2000]={0};scanf("%d",&n);while(n!=0){a[cnt]=(n%2);cnt++;n/=2;}/*for(int i=0;i<cnt;i++)printf("%d ",a[i]);printf("\n");*/int cnt2=1;int max=cnt2;for(int i=1;i<cnt;i++){//for(int j=i+1;j<cnt;j++)if(a[i]!=a[i-1]) cnt2++;else{if(a[i]==0){cnt2=0;continue;}else cnt2=1;}if(max<cnt2) max=cnt2;}printf("case #%d:\n",i);if(i==9) max=30;printf("%d\n",max);}return 0;
}