菜鳥記錄:c語言實現PAT甲級1010--Radix

来源:https://www.cnblogs.com/whf10000010/p/18109014
-Advertisement-
Play Games

很長時間沒做,忙於考研和實習,久違的的拾起了演算法。做了很長時間,其實總體思路還是很簡單的,但滿分不知道為什麼就是到不了,又因為網上很多答案包括柳神的都是c++,無法參透,姑且只能這樣了。 Given a pair of positive integers, for example, 6 and 11 ...


很長時間沒做,忙於考研和實習,久違的的拾起了演算法。做了很長時間,其實總體思路還是很簡單的,但滿分不知道為什麼就是到不了,又因為網上很多答案包括柳神的都是c++,無法參透,姑且只能這樣了。

Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number.

Now for any pair of positive integers N1 and N2, your task is to find the radix of one number while that of the other is given.

Input Specification:

Each input file contains one test case. Each case occupies a line which contains 4 positive integers:


N1 N2 tag radix

Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set { 0-9, a-z } where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number radix is the radix of N1 if tag is 1, or of N2 if tag is 2.

Output Specification:

For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.

Sample Input 1:

6 110 1 10

Sample Output 1:

2

Sample Input 2:

1 ab 1 2

Sample Output 2:

Impossible

題目分析:

一方面,N1和N2的數字輸入是不方便用int數組的,因該用字元串來分個存儲,這樣既方便又高效。另一方面,程式的整體流程就是:

  1. 輸入、存儲。
  2. 判斷tag,到這大概能寫出main函數,根據result變數確定輸出數字還是“impossible”
    int main() {
         int result;
         scanf("%s %s %d%d",&N1,&N2, &tag, &radix);
             if (tag == 1)
             {
                 result = Radix(N1, N2,radix );
             }
             else if(tag==2)
             {
                 result = Radix(N2,N1,radix);
             }
             else
             {
                 result = 0;
             }
    
         if (result != 0)
             printf("%d", result);
         else
             printf("Impossible");
        return 0;
     }  
    
  3. 編寫具體的轉換函數,結果返回到result。

個人想法:

主題函數很好寫,而且不需要在意題目中提到的出現多個可轉換的進位輸出最小進位,當你第一次遍歷得到正確進位數時就可以直接輸出。

轉換進位的函數Radix(char *tar,char *cha,int radix),tar數組直接按照radix寫一個for迴圈轉換為二進位,cha則多加一個for迴圈進行多個進位的遍歷,(這裡註意的是,不是只到36就可以的,我相同的程式在只遍歷36次時只有19分,遍歷過多又會有超時,最高在999999次時達到24分),轉換進位的代碼就好寫了。

 1 int Radix(char *tar,char *cha,int radix) {
 2     double sum1 = 0;
 3     for (int i = strlen(tar)-1; i >=0; i--)
 4     {
 5         double tmp;
 6         tmp = tar[i];
 7         if (tmp > '9')tmp = tmp - 'a' + 10;//a-z
 8         else if (tmp < 'a'&&tmp>='0')tmp -= '0';//0-9
 9         if (tmp >= radix) return 0;
10         sum1 += tmp * pow(radix,strlen(tar)-i-1);
11     }
12     for (int i = 0; i <= 999999;i++) {
13         double sum2 = 0;
14         for (int j = strlen(cha) - 1; j >= 0; j--) {
15             double tmp;
16             tmp = cha[j];
17             if (tmp > '9')tmp =tmp- 'a' + 10;//a-z
18             else if (tmp < 'a' && tmp >= '0')tmp -= '0';//0-9
19             if (tmp >= i) break;
20             sum2 += tmp * pow(i, strlen(cha) - j - 1);
21         }
22 
23         if (sum1 == sum2)return i;
24     }
25     return 0;
26 }

在多次調試時發現需要註意:

  1. 輸入N1和N2數組時, scanf("%s %s %d%d",&N1,&N2, &tag, &radix);%s後面必須有空格,這樣每個字元才會被分割到數組裡面。
  2. 求和變數sum2與sum1不同,需寫在for迴圈內,不然遍歷下一次時會sum2因為不會清0而不斷累加導致一直報錯。
  3. sizeof()求出來整個數組的長度,而strlen()求出有效長度。eg:110存入a[10],sizeof(a)=10.strlen(a)=3
  4. ‘110’在數組裡面的位置是0,1,2,機器看起來就是‘011’,反過來了,在求和時要反過來
  5. 輸入的數字大於當前進位是不可能的,所以直接退出或break就好(9和19行)

最後得到的整體代碼為:

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 #define _CRT_SECURE_NO_WARNINGS
 5 char N1[10],  N2[10];
 6 int tag, radix;
 7 int Radix(char* tar, char* cha, int radix);
 8  int main() {
 9      int result;
10      
11      scanf("%s %s %d%d",&N1,&N2, &tag, &radix);
12          if (tag == 1)
13          {
14              result = Radix(N1, N2,radix );
15          }
16          else if(tag==2)
17          {
18              result = Radix(N2,N1,radix);
19          }
20          else
21          {
22              result = 0;
23          }
24 
25      if (result != 0)
26          printf("%d", result);
27      else
28          printf("Impossible");
29     return 0;
30  }
31 int Radix(char *tar,char *cha,int radix) {
32     double sum1 = 0;
33     for (int i = strlen(tar)-1; i >=0; i--)
34     {
35         double tmp;
36         tmp = tar[i];
37         if (tmp > '9')tmp = tmp - 'a' + 10;//a-z
38         else if (tmp < 'a'&&tmp>='0')tmp -= '0';//0-9
39         if (tmp >= radix) return 0;
40         sum1 += tmp * pow(radix,strlen(tar)-i-1);
41     }
42     for (int i = 0; i <= 999999;i++) {
43         double sum2 = 0;
44         for (int j = strlen(cha) - 1; j >= 0; j--) {
45             double tmp;
46             tmp = cha[j];
47             if (tmp > '9')tmp =tmp- 'a' + 10;//a-z
48             else if (tmp < 'a' && tmp >= '0')tmp -= '0';//0-9
49             if (tmp >= i) break;
50             sum2 += tmp * pow(i, strlen(cha) - j - 1);
51         }
52 
53         if (sum1 == sum2)return i;
54     }
55     return 0;
56 }
View Code

結果:

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Ajax 與 Axios 非同步請求 一、伺服器對外提供了哪些資源 1. 網頁中如何請求數據 數據,也是伺服器對外提供的一種資源。只要是資源,必然要通過 請求 – 處理 – 響應 的方式進行獲取。如果要在網頁中請求伺服器上的數據資源,則需要用到 XMLHttpRequest 對象。XMLHttpReq ...
  • 網頁圖像漸變的方法(HTML+CSS)(漸變與切換) Date: 2024.03.27 參考 色彩 runoob-漸變色工具 漸變 - 水平多圖 效果 HTML <div class="conBox pubCon"> <div class="imgBox"> <img class="img1" sr ...
  • 客戶管理系統的應用架構設計 應用層定義了軟體系統的應用功能,負責接收用戶的請求,協調領域層能力來執行任務,並將結果返回給用戶,功能模塊包括: 客戶管理:核心功能模塊,負責收集和更新客戶信息,包括個人資料、聯繫方式、消費習慣、會員卡、歸屬信息(比如銷售或顧問)和備註。這個模塊是CRM系統的基礎,支撐其 ...
  • C++ 數學 C++ 有許多函數可以讓您在數字上執行數學任務。 最大值和最小值 max(x, y) 函數可用於找到 x 和 y 的最大值: 示例 cout << max(5, 10); 而 min(x, y) 函數可用於找到 x 和 y 的最小值: 示例 cout << min(5, 10); C+ ...
  • 1 枚舉好用嗎? 數據字典型欄位,枚舉比Integer好: 限定值,只能賦值枚舉的那幾個實例,不能像Integer隨便輸,保存和查詢的時候特別有用 含義明確,使用時不需要去查數據字典 顯示值跟存儲值直接映射,不需要手動轉換,比如1在頁面上顯示為啟用,0顯示禁用,枚舉定義好可以直接顯示 基於enum可 ...
  • 本文基於 OpenJDK17 進行討論 在 JDK NIO 針對堆外記憶體的分配場景中,我們經常會看到 System.gc 的身影,比如當我們通過 FileChannel#map 對文件進行記憶體映射的時候,如果 JVM 進程虛擬記憶體空間中的虛擬記憶體不足,JVM 在 native 層就會拋出 OutOf ...
  • 問題描述 問題和 unordered_set 有關,相關代碼如下: //列印unordered_set的所有值 void printSet(const std::unordered_set<std::string> &data) { int index = 0; auto it = data.beg ...
  • 本文介紹在Anaconda環境下,安裝Python讀取.xls格式表格文件的庫xlrd的方法。 xlrd是一個用於讀取Excel文件的Python庫,下麵是xlrd庫的一些主要特點和功能: 讀取Excel文件:xlrd可以打開和讀取Excel文件,並提取其中的數據和元數據。 支持多種數據類型:xlr ...
一周排行
    -Advertisement-
    Play Games
  • 隨著Aspire發佈preview5的發佈,Microsoft.Extensions.ServiceDiscovery隨之更新, 服務註冊發現這個屬於老掉牙的話題解決什麼問題就不贅述了,這裡主要講講Microsoft.Extensions.ServiceDiscovery(preview5)以及如何 ...
  • 概述:通過使用`SemaphoreSlim`,可以簡單而有效地限制非同步HTTP請求的併發量,確保在任何給定時間內不超過20個網頁同時下載。`ParallelOptions`不適用於非同步操作,但可考慮使用`Parallel.ForEach`,儘管在非同步場景中謹慎使用。 對於併發非同步 I/O 操作的數量 ...
  • 1.Linux上安裝Docken 伺服器系統版本以及內核版本:cat /etc/redhat-release 查看伺服器內核版本:uname -r 安裝依賴包:yum install -y yum-utils device-mapper-persistent-data lvm2 設置阿裡雲鏡像源:y ...
  • 概述:WPF界面綁定和渲染大量數據可能導致性能問題。通過啟用UI虛擬化、非同步載入和數據分頁,可以有效提高界面響應性能。以下是簡單示例演示這些優化方法。 在WPF中,當你嘗試綁定和渲染大量的數據項時,性能問題可能出現。以下是一些可能導致性能慢的原因以及優化方法: UI 虛擬化: WPF提供了虛擬化技術 ...
  • 引言 上一章節介紹了 TDD 的三大法則,今天我們講一下在單元測試中模擬對象的使用。 Fake Fake - Fake 是一個通用術語,可用於描述 stub或 mock 對象。 它是 stub 還是 mock 取決於使用它的上下文。 也就是說,Fake 可以是 stub 或 mock Mock - ...
  • 為.net6在CentOS7上面做準備,先在vmware虛擬機安裝CentOS 7.9 新建CentOS764位的系統 因為CentOS8不更新了,所以安裝7;簡單就一筆帶過了 選擇下載好的操作系統的iso文件,下載地址https://mirrors.aliyun.com/centos/7.9.20 ...
  • 經過前面幾篇的學習,我們瞭解到指令的大概分類,如:參數載入指令,該載入指令以 Ld 開頭,將參數載入到棧中,以便於後續執行操作命令。參數存儲指令,其指令以 St 開頭,將棧中的數據,存儲到指定的變數中,以方便後續使用。創建實例指令,其指令以 New 開頭,用於在運行時動態生成並初始化對象。方法調用指... ...
  • LiteDB 是一個輕量級的嵌入式 NoSQL 資料庫,其設計理念與 MongoDB 類似,但它是完全使用 C# 開發的,因此與 C# 應用程式的集成非常順暢。與 SQLite 相比,LiteDB 提供了 NoSQL(即鍵值對)的數據存儲方式,並且是一個開源且免費的項目。它適用於桌面、移動以及 We ...
  • 1 開源解析和拆分文檔 第三方的工具去對文件解析拆分,去將我們的文件內容給提取出來,並將我們的文檔內容去拆分成一個小的chunk。常見的PDF word mark down, JSON、HTML。都可以有很好的一些模塊去把這些文件去進行一個東西去提取。 優勢 支持豐富的文檔類型 每種文檔多樣化選擇 ...
  • OOM是什麼?英文全稱為 OutOfMemoryError(記憶體溢出錯誤)。當程式發生OOM時,如何去定位導致異常的代碼還是挺麻煩的。 要檢查OOM發生的原因,首先需要瞭解各種OOM情況下會報的異常信息。這樣能縮小排查範圍,再結合異常堆棧、heapDump文件、JVM分析工具和業務代碼來判斷具體是哪 ...