SZU:J38 Number Base Conversion

2024-06-02 04:08
文章标签 number conversion base szu j38

本文主要是介绍SZU:J38 Number Base Conversion,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Judge Info

  • Memory Limit: 32768KB
  • Case Time Limit: 1000MS
  • Time Limit: 1000MS
  • Judger: Number Only Judger

Description

现在假设:
2进制对应的基数是0,1;
3进制对应的基数是0,1,2;
……
10进制对应的基数是0,1,2,3,4,5,6,7,8,9.
……
n进制对应的基数是0,1,2,3,……,n-1;
你的任务是实现进制之间的转换。

Input

第一行,有t(t<=1000),表示测试数据的个数。 接下来每行2个正整数n,m,分别代表 一个十进制的数n(n<10^100),和需要转成m(2<=m<100)进制的m。

Output

对于每组测试,输出转换之后的数。

Sample Input

3
19 17
19 5
51642140186286313 50

Sample Output

12
34
2622146482940142613

 

解题思路:刚开始本来应该用 BigInteger 这种大数类来做。但写起来很复杂,就换了一种方法。

12是一个十位数,十位上是1,个位上是2.

我们发现在第一轮运算时,十位上的1作为被除数,2作为除数,得到的商是0,余数是1(可以断言只考虑当前这一个数位的计算,余数或是0,或是1,若是1的话,则进入下一数位(这里即对个位进行运算)时,要用1乘上进制(这里是10)再加上下一个数位上的值(这里是2)),即得到运算进入个位时被除数是12,除数是2,得到的商是6,余数是0。第一轮运算的结果是商是06,余数是0.

进入第二轮运算,则上一轮的商6(这里首先要去掉前面多余的0)变成本轮的被除数,如此下去,即可得到每轮的余数。

推广开来,如果被除数是一个1000位的大数,例如“12343435154324123……342314324343”

那么我们照样可以从第一个数位开始逐位考虑,比如第一位是1(作为被除数),2是除数,得到的商是0,余数是1,然后是第二个数位2,由于上一位留下了余数1,则此时被除数应该是1*10+2 = 12,所以得到的商是6,余数是0,即运算到此时的商是06,然后是第三个数位3,由于上一个数位留下的余数是0,所以此时被除数就是3,。。。如此下去就完成第一轮的运算,

这一轮完毕后,需要把得到的商变成下一轮的被除数,继续上述的运算,直到被除数为0才停止

代码:

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 char str[1000];//输入字符串
 5 int start[500],ans[500],res[500]; //被除数,商,余数
 6 
 7 //转换前后的进制
 8 int oldBase = 10;
 9 int newBase = 50;
10 
11 void change()
12 {//各个数位还原为数字形式
13     int i,len = strlen(str);
14     start[0] = len;
15     for(i=1;i<= len;i++)
16     {
17         if(str[i-1] >= '0' && str[i-1] <= '9')
18         {
19             start[i] = str[i-1] - '0';
20         }
21     } 
22 }
23 
24 void solve()
25 {
26     memset(res,0,sizeof(res));//余数初始化为空
27     int y,i,j;
28     //模n取余法,(总体规律是先余为低位,后余为高位)
29     while(start[0] >= 1)
30     {//只要被除数仍然大于等于1,那就继续“模2取余”
31         y=0;
32         i=1;
33         ans[0]=start[0];
34         //
35         while(i <= start[0])
36         {
37             y = y * oldBase + start[i];
38             ans[i++] = y/newBase;
39             y %= newBase; 
40         }
41         res[++res[0]] = y;//这一轮运算得到的余数
42         i = 1;
43         //找到下一轮商的起始处
44         while((i<=ans[0]) && (ans[i]==0)) i++;
45         //清除这一轮使用的被除数
46         memset(start,0,sizeof(start));
47         //本轮得到的商变为下一轮的被除数
48         for(j = i;j <= ans[0];j++)
49             start[++start[0]] = ans[j]; 
50         memset(ans,0,sizeof(ans)); //清除这一轮的商,为下一轮运算做准备
51     } 
52 }
53 
54 void output()
55 {//从高位到低位逆序输出
56     int i;
57     int flag=0;
58     for(i = res[0];i >= 1;--i)
59     {  
60         printf("%d",res[i]);
61     }
62     printf("\n"); 
63 }
64 
65 int main()
66 {
67     int t;
68     scanf("%d", &t);
69     while(t--){
70         scanf("%s",str);
71         scanf("%d", &newBase);
72         change();
73         solve();
74         output();
75     }
76     return 0;
77 }

 

这篇关于SZU:J38 Number Base Conversion的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1022994

相关文章

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

Retrieval-based-Voice-Conversion-WebUI模型构建指南

一、模型介绍 Retrieval-based-Voice-Conversion-WebUI(简称 RVC)模型是一个基于 VITS(Variational Inference with adversarial learning for end-to-end Text-to-Speech)的简单易用的语音转换框架。 具有以下特点 简单易用:RVC 模型通过简单易用的网页界面,使得用户无需深入了

题目1380:lucky number

题目1380:lucky number 时间限制:3 秒 内存限制:3 兆 特殊判题:否 提交:2839 解决:300 题目描述: 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然

Jenkins 通过 Version Number Plugin 自动生成和管理构建的版本号

步骤 1:安装 Version Number Plugin 登录 Jenkins 的管理界面。进入 “Manage Jenkins” -> “Manage Plugins”。在 “Available” 选项卡中搜索 “Version Number Plugin”。选中并安装插件,完成后可能需要重启 Jenkins。 步骤 2:配置版本号生成 打开项目配置页面。在下方找到 “Build Env

docker学习系列(四)制作基础的base项目镜像--jdk+tomcat

前面已经完成了docker的安装以及使用,现在我们要将自己的javaweb项目与docker结合 1.1准备jdk+tomcat软件 ​​我下载了apache-tomcat-7.0.68.tar.gz和jdk-7u79-linux-x64.tar.gz,存储于Linux机器的本地目录/usr/ect/wt/下(利用xshell上传)。利用linux命令 tar -zxvf apache-tom

【Hdu】Minimum Inversion Number(逆序,线段树)

利用线段树在nlogn的时间复杂度内求一段数的逆序。 由于给的序列是由0 ~ n -1组成的,求出初始的逆序之后可以递推出移动之后的逆序数。 #include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const in

【JavaScript】基本数据类型与引用数据类型区别(及为什么String、Boolean、Number基本数据类型会有属性和方法?)

基本数据类型   JavaScript基本数据类型包括:undefined、null、number、boolean、string。基本数据类型是按值访问的,就是说我们可以操作保存在变量中的实际的值。 1)基本数据类型的值是不可变的 任何方法都无法改变一个基本类型的值,比如一个字符串: var name = "change";name.substr();//hangconsole.log

Base64编码 及 在HTML中用Base编码直接显示图片或嵌入其他文件类型

1.为什么要用到BASE64编码的图片信息      Base64是网络上最常见的用于传输8Bit字节代码的编码方式之一。Base64 主要不是加密,它主要的用途是把一些二进制数转成普通字符用于网络传输。由于一些二进制字符在传输协议中属于控制字符,不能直接传送需要转换一下。最常见的用途是作为电子邮件或WebService附件的传输编码.  2.base64编码定义    目前的internet

ORA-24067: exceeded maximum number of subscribers for queue ADMIN.SMS_MT_QUEUE

临时处理办法: delete from aq$_ss_MT_tab_D;delete from aq$_ss_MT_tab_g;delete from aq$_ss_MT_tab_h;delete from aq$_ss_MT_tab_i;delete from aq$_ss_MT_tab_p;delete from aq$_ss_MT_tab_s;delete from aq$

SQLSERVER排名函数RANK,DENSE_RANK,NTILE,ROW_NUMBER

SQL SERVER排名函数RANK,DENSE_RANK,NTILE,ROW_NUMBER 前言 本文意于用实例数据帮助理解SQL SERVER排名函数RANK,DENSE_RANK,NTILE,ROW_NUMBER。 准备工作 创建测试表:   ? 1 2 3 4 5 create table test( id int identity(1,1)