本人第一篇博客，剛學演算法半年的蒟蒻，用于進一步學習交流，
分~界~線~~~
進制轉換
題目描述：
將一個長度最多為30位數字的十進制非負整數轉換為二進制數輸出，
輸入：
多組資料，每行為一個長度不超過30位的十進制非負整數，
（注意是10進制數字的個數可能有30個，而非30bits的整數）
輸出：
每行輸出對應的二進制數，
樣例輸入：
985 211 1126
樣例輸出：
1111011001 11010011 10001100110
注：每段代碼變數不一致，以最后Code為標準，
分析：
每組資料輸入長度不超過30位的十進制非負數，
不是30bits！不是30bits！不是30bits！
按照大數的一般操作，我們可以先用字符陣列存盤后，再進一步用整型陣列存盤，以便后續轉為二進制，
char str[35]; int num[35]; for(int len=0;str[len];++len){ num[len]=str[len]-'0'; }
進制轉換，從十進制 -> x 進制，一般操作（應該沒有其他辦法了吧_小聲_）是將十進制數 n 對 x 取模結果存入ans陣列內（ 我是用ans陣列存放轉換成的二進制答案的 ），然后通過 n /= x 更新 n 的值，
int i=0; int n,x; int ans[MAXN]; do{ ans[i++] = n % x; n /= x; }while(n);
問題：
如果是普通整型范圍內的非負整數是能直接進行運算的（或者用python，手動滑稽），本題資料均是超過30位的非負整數，就需要用到大數除以及取模操作，開始時，我能想到的只有暴力，顯然，暴力不能解決問題，于是我就..打開了萬能的百度......
本題特別的由十進制轉二進制，在轉二進制時，如何判斷當前數值取模結果，主要在于當前十進制數末位奇偶狀態，奇數為1，偶數為0，
int len = strlen(str); ans = num[len-1]%2;
取模后，需要用當前數除進制數 ”2“得新數 ，按照除法運算的規則，可以明顯發現，被除數當前位為奇時，借給下一位的值為10，反之為0，可以用和大整數加法類似的變數 x 來存盤借位值，
int i,tmp,l=0,x=0; for(i=l;i<len;++i){ tmp=num[i]; num[i]=(num[i]+x)/2; if(tmp&1)x=10; else x=0; } if(num[l]==0)++l;
我是選擇在原值上進行修改，用 ' l ' 來記錄十進制數最高位的位置，除數小于10，因此每次最高位的位數最多向右移一位，即若當前最高位的數值為0，就說明最高位已經向后移動一位，
Code：
代碼如下，注釋有空再加...
#include<iostream> #include<cstdio> using namespace std; char str[35]; int num[35]; int ans[1005]; int main(){ int i,j; int len=0,tmp; int x,l; while(scanf("%s",str)!=EOF){ for(len=0;str[len];++len){ num[len]=str[len]-'0'; } j=0; l=0; while(l<len){ ans[j++]=num[len-1]%2; x=0; for(i=l;i<len;++i){ tmp=num[i]; num[i]=(num[i]+x)/2; if(tmp&1)x=10; else x=0; } if(num[l]==0)++l; } for(i=j-1;i>=0;--i){ printf("%d",ans[i]); } printf("\n"); } return 0; }
識訓：
在做大整數進制轉換的時候，遇到二進制可以特殊對待，相似的是，有些問題也是如此，
十進制轉二進制，末尾奇偶確定取模結果，當前位奇偶確定借位值大小，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/281145.html
標籤：其他