追蹤狀態——消息解碼問題的思路剖析

来源:http://www.cnblogs.com/OctoptusLian/archive/2017/01/22/6337709.html
-Advertisement-
Play Games

題目描述 一條消息被編碼為一個文本流，被逐字元地讀取。這個流包含了一系列由逗號分隔的整數，每個整數都可以用C的int類型表示。但是，一個特定整數所表示的字元取決於當前的解碼模式。共有3種這樣的模式：大寫字母、小寫字母和標點符號。 在大寫字母模式下，每個整數表示一個大寫字母：這個整數除以27的餘數表示 ...


題目描述 

一條消息被編碼為一個文本流，被逐字元地讀取。這個流包含了一系列由逗號分隔的整數，每個整數都可以用C的int類型表示。但是，一個特定整數所表示的字元取決於當前的解碼模式。共有3種這樣的模式：大寫字母、小寫字母和標點符號。

在大寫字母模式下，每個整數表示一個大寫字母：這個整數除以27的餘數表示字母表中的具體字母（其中1=A，接下來以此類推）。因此，大寫字母模式中的143這個值表示字母H，因為143除以27的餘數為8，而H正是字母表中的第8個字母。

小寫字母模式的機制類似，只不過表示的是小寫字母。整數除以27的餘數表示小寫字母（1=a，接下來以此類推）。因此，在小寫字母模式下，56這個值表示字母b，因為56除以27的餘數是2，而b正是字母表中的第2個字母。

在標點符號模式下，是把整數除以9求餘，下表給出了不同餘數的解釋。19表示感嘆號，因為19除以9的餘數是1。

編號 符號
1 ！
2 ？
3 ，
4 .
5 （空格）
6 ；
7 "
8 \'

下麵我們通過一張圖來理解下消息解碼問題的處理（B-大寫模式；X-小寫模式；D-標點符號模式）：

a列顯示了輸入中的當前數字；b列是當前的模式；c列顯示了當前模式的除數；d列是a列的當前輸入除以c列的除數所得到的餘數；e列顯示了結果。

問題分析與分解：

我們需要讀取一個字元串，直到讀取到行末符。這些字元表示一系列的整數，因此需要讀取這些數字字元並把它們轉換為整數以便進行處理。有了這些整數之後，需要把他們轉換為單個字元進行輸出。最後我們需要一些方法處理解碼模式，以便知道當前的整數應該被解碼為小寫字母、大寫字母還是標點符號。我們首先把這些需要完成的任務進行分解：

  • 逐個讀取字元，直到讀取了行末符。
  • 把表示一個數的一系列字元轉換為一個整數。
  • 把一個1~26之間的整數轉換為一個大寫字母。
  • 把一個1~26之間的整數轉換為一個小寫字母。
  • 把一個1~8之間的整數轉換為一個標點符號。
  • 追蹤一種解碼模式。

讓我們從整數到字元的轉換開始

從Luhn公式程式中，我們知道需要讀取一個0~9範圍內的字元數字，並把它轉換為0~9範圍的整數。我們怎麼才能擴展這種方法，使之能夠處理多位數呢？讓我們考慮最簡單的可能性：兩位數。這看上去非常簡單。在兩位數中，第一個數字是十位數，因此我們應該把這個數字乘以10，然後與第二個數字所表示的值相加。例如：輸入一個數為35，我們用程式以字元的形式分別讀取了3和5之後，把它們分別轉換為整數3和5，然後通過表達式3*10+5得到總的整數。我們可以用代碼來驗證一下：

1     char digitChart1,digitChart2;
2     printf("Enter a two-digit number:");
3     scanf("%c",&digitChart1);
4     scanf("%c",&digitChart2);
5     int digit1 = digitChart1 - '0';
6     int digit2 = digitChart2 - '0';
7     int overallNumber = digit1 * 10 + digit2;
8     printf("That number as an integer:%d",overallNumber);

運行結果為：

這段代碼達到了輸出了我們輸入的相同的兩位數。但是，這個程式使用兩個不同的變數保存兩個字元輸入，雖然它在當前不會有什麼問題，但顯然不適合作為一種通用的解決方案。如果採用這樣的做法，我們所需要的變數數量就和輸入的數字一樣多。這很容易造成混亂，並且如果輸入流發生了變化就很難修改輸入數據的字數範圍。對於把字元變換為整數的這個子任務，我們需要一種更通用的解決方案。尋找這種通用的解決方案的第一個步驟是對前面的代碼進行限制，使它只能使用2個變數，1個char變數和1個int變數：

1     char digitChart;
2     printf("Enter a two-digit number:");
3     scanf("%c",&digitChart);  //讀取第一個字元數字 
4     int overallNumber = (digitChart - '0') * 10;  //把它轉換為整數並乘以10，然後存儲結果 
5     scanf("%c",&digitChart);  //讀取第二個數字 
6     overallNumber += (digitChart - '0');
7     printf("That number as an integer:%d",overallNumber);

它的功能與前面的代碼相同，區別在於只使用了兩個變數：一個表示最近所讀取的字元，一個表示整數的總值。

下一個步驟是考慮這樣對這個方法進行擴展，使之適用於三位數。一旦完成了這個任務之後，我們很可能會發現一種模式，可以為任意位數的整數創建一個通用的解決方案。

但是我們不知道要處理的數有多少個數字，所以我們可以試著：編寫一個程式，逐字元讀取一個數，並把它轉換為整數，只能使用1個char變數和1個int變數，這個數可能由3個或4個數字組成。

由於我們只能使用1個數值變數，如果沒有思路，可以先放寬這個限制，以便取得一些進展，所以簡化後的問題為：編寫一個程式，逐字元讀取一個數，並把它轉換為整數，只能使用1個char變數和2個int變數，這個數可能由3個或4個數字組成。

現在我們可以把“雙管齊下”的計算方法付諸實施。我們將用兩種不同的方式處理前3位數字，然後看看是否存在第4位數字：

 1     char digitChar;
 2     printf("Enter a three-digit number:");
 3     scanf("%c",&digitChar);
 4     int threeDigitNumber = (digitChar - '0') * 100;  //讀取最左邊的數字之後，把它的整數值乘以100，並把它存儲在表示三位數的變數中 
 5     int fourDigitNumber = (digitChar - '0') * 1000;
 6     scanf("%c",&digitChar);
 7     threeDigitNumber += (digitChar - '0') * 10;
 8     fourDigitNumber += (digitChar - '0') * 100;
 9     scanf("%c",&digitChar);
10     threeDigitNumber += (digitChar - '0');
11     fourDigitNumber += (digitChar - '0') * 10;
12     scanf("%c",&digitChar);
13     if(digitChar == 10)  //在讀取了第4個字元之後，我們把它與10這個數進行比較，確定它是否為行末符 
14         printf("Number entered:%d\n",threeDigitNumber);  //如果是，那麼所輸入的值就是個三位數 
15     else
16         printf("Number entered:%d\n",fourDigitNumber);  //如果不是，我們需要把它作為最後一個數字添加到總和中

運行結果為：     

 現在，我們需要確定怎樣去掉其中一個整型變數。假設我們完全去掉了fourDigitNumber變數，threeDigitNumber仍然是被正確賦值的。但是當我們需要fourDigitNumber時，就沒辦法再得到它了。使用threeDigitNumber的值，是否還有辦法確定fourDigitNumber的值呢？假設原始輸入為1234，在讀取了前3個數字之後，threeDigitNumber變數的值將是123，此時fourDigitNumber的值應該是1230。一般而言，由於在計算過程中fourDigitNumber的每個乘數都是threeDigitNumber的對應乘數的10倍，因此前者的值總是後者的10倍。所以我們只需要使用1個整型變數，因為在必要的情況下只要乘以10就可以得到另一個變數的值：

 1     char digitChar;
 2     printf("Enter a three-digit number:");
 3     scanf("%c",&digitChar);
 4     int number = (digitChar - '0') * 100;
 5     scanf("%c",&digitChar);
 6     number += (digitChar - '0') * 10;
 7     scanf("%c",&digitChar);
 8     number += digitChar - '0';
 9     scanf("%c",&digitChar);
10     if(digitChar == 10)   
11         printf("Number entered:%d\n",number);  
12     else{
13         number = number * 10 + (digitChar - '0');
14         printf("Number entered:%d\n",number); 
15     }

運行結果為：

現在我們已經有了一個可利用的模式。考慮把這段代碼擴展到可以處理五位數：

 1     char digitChar;
 2     printf("Enter a number with three,four,five digits:");
 3     scanf("%c",&digitChar);
 4     int number = (digitChar - '0') * 100;
 5     scanf("%c",&digitChar);
 6     number += (digitChar - '0') * 10;
 7     scanf("%c",&digitChar);
 8     number += digitChar - '0';
 9     scanf("%c",&digitChar);
10     if(digitChar == 10)    
11         printf("Number entered:%d\n",number);    
12     else{
13         number = number * 10 + (digitChar - '0');
14         scanf("%c",&digitChar);
15         if(digitChar == 10){  //檢查它是否表示行末符
16             printf("Number entered:%d\n",number); //如果是，就顯示之前計算所得的數
17         }
18         else{
19             number = number * 10 + (digitChar - '0');  //否則就把它乘以10，再加上當前字元所表示的整數數值 
20             printf("Number entered:%d\n",number);
21         }
22     }

 

運行結果為：  

 

我想現在這個模式已經非常清晰了：如果下一個字元非行末符，就可以將當前的數乘以10，然後與當前字元所表示的整數值相加。理解了這一點，我們就可以編寫一個迴圈，處理任意長度的整數了：

 1     char digitChar;
 2     printf("Enter a number with as many digits as you like:");
 3     scanf("%c",&digitChar);  //讀取第一個字元 
 4     int number = (digitChar - '0');  //確定它的整數值 
 5     scanf("%c",&digitChar);  //讀取第二個字元併進入迴圈 
 6     while(digitChar != 10){  //檢查最近所讀取的那個字元是否為行末符 
 7         number = number * 10 + (digitChar - '0');  //如果不是，就把當前為止的和乘以10，並與當前字元的整數值相加 
 8         scanf("%c",&digitChar);  //然後讀取下一個字元 
 9     }
10     printf("Numbered entered:%d\n",number);  //一旦讀入了行末符，表示當前整數的變數number就包含了可以輸出的整數值

運行結果為：

這段代碼用於處理一系列的字元到對應的整數值的轉換。在最終的程式中，我們將讀取一系列由逗號分隔的數，而且每個數必須單獨讀取並處理。

讓我們考慮下101,22[EOF]（行末符）這個輸入，對迴圈的測試條件進行修改，對行末符或逗號進行檢查是很輕鬆的。接著，我們需要把處理一個數的迴圈放在一個更大的迴圈中，後者在所有的數被讀取之前將一直持續。因此，內層迴圈在讀取到[EOF]或逗號時將會結束，而外層迴圈只有在讀取到[EOF]時才會結束：

 1     char digitChar;
 2     do{
 3         scanf("%c",&digitChar);
 4         int number = (digitChar - '0');  
 5         scanf("%c",&digitChar); 
 6         while((digitChar != 10)&&(digitChar != ',')){  //內迴圈 
 7             number = number * 10 + (digitChar - '0');
 8             scanf("%c",&digitChar);
 9         }
10         printf("Number entered:%d\n",number);
11     }while(digitChar != 10);  //外迴圈

運行結果為：

下麵我們可以把註意力集中在處理單獨的數上了

把一個範圍在1~26之間的數轉換為一個A~Z範圍內的字母，稍微想一下，就可以發現它實際上是把單個數字字元轉換為對應整數值的逆操作。如果我們減去0的字元碼，能夠從0~9範圍的字元碼轉換為0~9範圍的整數值，那麼應該也能夠通過加上一個字元碼，從1~26轉換為A~Z。我們先試試加上'A'會怎麼樣：

1     printf("Enter a number 1-26:");
2     int number;
3     scanf("%d",&number);
4     char outputCharacter;
5     outputCharacter = number + 'A';
6     printf("Equivalent symbol:%c\n",outputCharacter);

運行結果為：

結果顯然不正確！字母表中的第五個字母是E而不是F。出現問題的原因是我們從1開始的範圍加上一個數的，當我們從另一個方向進行轉換，把一個字元數字轉換為對應的整數值時，我們所處理的範圍應該是從0開始的。所以我們可以把第5行的代碼改成number + 'A' - 1來修正這個問題。

因為表中的標點符號在ASCII或其他任何字碼符系統中都不是按照這個順序出現的，因此我們必須用窮舉法處理這個標點符號表轉換的問題：

 1     printf("Enter a number 1-8:");
 2     int number;
 3     scanf("%d",&number);
 4     char outputCharacter;
 5     switch(number){
 6         case 1:outputCharacter = '!';break;
 7         case 2:outputCharacter = '?';break;
 8         case 3:outputCharacter = ',';break;
 9         case 4:outputCharacter = '.';break;
10         case 5:outputCharacter = ' ';break;
11         case 6:outputCharacter = ';';break;
12         case 7:outputCharacter = '"';break;
13         case 8:outputCharacter = '\'';break; //使用反斜杠作為轉義符，以顯示單引號 
14     }
15     printf("Equivalent symbol:%c\n",outputCharacter);

還有一個子問題：當最近讀取值的解碼結果為0時，就進行模式的轉換。

根據最開始的問題描述，知道了我們需要的就是一個存儲當前模式的變數，並把邏輯放在“讀取並處理下一個值”的迴圈中，在必要的時候切換模式。追蹤當前模式的變數可以是個簡單的整數，但是使用枚舉顯然可以使代碼更容易理解。一個很好的經驗是：如果一個變數只用於追蹤一個狀態，並且任何特定的值並沒有內在的含義，那麼使用枚舉法就很好了。下麵根據這個思路寫下代碼：

 1     enum modeType{UPPERCASE,LOWERCASE,PUNCTUATION};   //枚舉型
 2     int number;
 3     modeType mode = UPPERCASE;
 4     printf("Enter some numbers ending with -1:");
 5     do{
 6         scanf("%d",&number);
 7         printf("Number read:%d",number);
 8         switch(mode){
 9             case UPPERCASE:
10                 number = number%27;
11                 printf(". Modulo 27:%d.",number);
12                 if(number == 0){
13                     printf("Switch to LOWERCASE");
14                     mode = LOWERCASE;
15                 }
16                 break;
17             case LOWERCASE:
18                 number = number%27;
19                 printf(". Modulo 27:%d.",number);
20                 if(number == 0){
21                     printf("Switch to PUNCTUATION");
22                     mode = PUNCTUATION;
23                 }
24                 break;
25             case PUNCTUATION:
26                 number = number%9;
27                 printf(". Modulo 9:%d.",number);
28                 if(number == 0){
29                     printf("Switch to UPPERCASE");
30                     mode = UPPERCASE;
31                 }
32                 break;
33         }
34         printf("\n");
35     }while(number != -1);

運行結果為：

 

此時，我們創建了一系列的建築塊，這是最艱苦的工作，現在的任務是把它們裝配在一起。

開始AC！！！！

 1     char outputCharacter;
 2     enum modeType{UPPERCASE,LOWERCASE,PUNCTUATION};   //枚舉型
 3     modeType mode = UPPERCASE;
 4     char digitChar;
 5      do{
 6          scanf("%c",&digitChar);
 7         int number = (digitChar - '0');  
 8         scanf("%c",&digitChar); 
 9         while((digitChar != 10)&&(digitChar != ',')){  //內迴圈 
10           number = number * 10 + (digitChar - '0');
11           scanf("%c",&digitChar);
12         }
13         switch(mode){
14             case UPPERCASE:
15                 number = number%27;
16                 outputCharacter = number + 'A' -1;
17                 if(number == 0){
18                     mode = LOWERCASE;
19                     continue;
20                 }
21                 break;
22             case LOWERCASE:
23                 number = number%27;
24                 outputCharacter = number + 'a' -1;
25                 if(number == 0){
26                     mode = PUNCTUATION;
27                     continue;
28                 }
29                 break;
30             case PUNCTUATION:
31                 number = number%9;
32                 switch(number){
33                                  case 1:outputCharacter = '!';break;
34                                 case 2:outputCharacter = '?';break;
35                                 case 3:outputCharacter = ',';break;
36                                 case 4:outputCharacter = '.';break;
37                                 case 5:outputCharacter = ' ';break;
38                                 case 6:outputCharacter = ';';break;
39                                 case 7:outputCharacter = '"';break;
40                                 case 8:outputCharacter = '\'';break;  
41                  }
42                 if(number == 0){
43                     mode = UPPERCASE;
44                     continue;
45                 }
46                 break;
47         }
48         printf("%c",outputCharacter);
49    }while(digitChar != 10);  //外迴圈 
50    printf("\n");

運行結果：

 

尾聲：此次練習增強了自己解決問題的信心。把複雜的問題分解成幾個小問題，然後逐個擊破。好了，就先寫到這，晚安！


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

-Advertisement-
Play Games
更多相關文章
  • Centos 7 搭建.net web項目
    現在的.NET Core 1.0版本是一個很小的核心，APIs和工具也並不完整，但是隨著.Net Core的不斷完善，補充的Apis和創新也會一起整合到.NET Framework中。 安裝centos系統 請自行安裝或百度教程 安裝 libicu包 和 dotnet 溫馨提示：如果需要用vsc編輯 ...
  • C# 最齊全的上傳圖片方法
    方法里包括了圖片大小限制、圖片尺寸、文件內容等等的判斷。。。 該案例是mvc下的demo，支持單張圖片上傳。 一般處理程式 csharp public void ProcessRequest(HttpContext context) { context.Response.ContentType = ...
  • 關於C#調用廣州醫保HG_Interface.dll調用的一些總結（外部組件異常）
    關於C#調用廣州醫保HG_Interface.dll調用的一些總結（外部組件異常） ...
  • SuperSocket入門（三）-Telnet多服務實例和服務實例交互配置詳解
    在SuperSocket入門(二)中我們已經簡單瞭解了通過配置App.config文件使用BootStrap啟動SuperSocket服務。我們先來看一下上個案例中的基本配置文件示例： <?xml version="1.0" encoding="utf-8"?> <configuration> <c ...
  • 一般處理程式、ASP.NET和MVC的區別
    這個問題說起來，我有點慚愧 想當初在大學里學的就是ASP.NET WebForms 在實習期間也是用的WebForms來開髮網站，然後就覺得.NET開髮網站就是用這個開發模式 現在想想都想笑。。。實在忍不住了，我要笑了。哈哈哈！！！ 好，回到正題 ASP.NET 是一個使用 HTML、CSS、Jav ...
  • c#核心基礎--類的構造方法
    一、構造方法 類的構造方法是類的成員方法的一種，它的作用是對類中的成員進行初始化操作。類的構造方法分為： 1.靜態構造方法 2.實例構造方法 1.靜態構造方法 類的靜態構造方法是類的成員方法的一種，它的作用是對類中的靜態成員進行初始化操作。下麵請看代碼實例： 1 using System; 2 na ...
  • WebApi關於配置全局返回Json數據格式時間以及命名小寫
    1.直接在Global文件中配置： 1 var formatters = GlobalConfiguration.Configuration.Formatters; 2 var jsonFormatter = formatters.JsonFormatter; 3 var settings = js... ...
  • macOS Sierra安裝Apache2.4+PHP7.0+MySQL5.7.16
    Mac系統上雖然自帶PHP和Apache，但是有時不是我們想要的版本呢。今天我們就在macOS Sierra(10.12.1)上安裝比較新的版本的PHP版本，也就是PHP7.0+了。本篇博客我們安裝的Apache是2.4的版本, MySQL5.7.16。稍後會詳細介紹這一過程。 一、安裝前的準備 1 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類