3.1-CaesarCipher-Lab

解題心得:
為了修正輸入k值很小很小的問題我想了好久，之後直接用計算機找出26的n次方加上去 >__<
但更好的方法是甚麼呢?

程式碼:

#include <iostream>
#include <string>
using namespace std;

int main() {
 long long int k;
 string plaintext;
 while (getline(cin, plaintext))
 {
  cin >> k;
  cin.ignore();
  for (int i = 0; i < plaintext.size(); i++)
  {
   if ('a' <= plaintext[i] && plaintext[i] <= 'z')
   {
    plaintext[i] = (plaintext[i] - 'a' + k + 208827064576) % 26 + 'a';

   }
   else if (plaintext[i] != ' ')
    plaintext[i] += 'a';
  }
  cout << plaintext << endl;
 }
 
 

 
    return 0;
}

3.2-RowTranspositionCipher-Lab

解題心得:
記得stringstream使用要初始化.....抓好久這個bug.......

程式碼:

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;

int main() {
 string plaintext;
 stringstream ss;
 while (getline(cin, plaintext))
 {
  int temp, row = 0;
  vector<int> key;
  string s;
  ss.clear();
  ss.str("");
  getline(cin, s);
  ss << s;
  while (ss >> temp) // get each key
  {
   key.push_back(temp);
   row++;
  }
  char array[10000][10000] = { '\0' };
  for (int i = 0; i < plaintext.size(); i++) // replace the data
  {
   if (plaintext[i] == ' ')
    array[i % row][i / row] = '_';
   else
    array[i % row][i / row] = plaintext[i];
  }
  for (int i = 0; i < row; i++)
  {
   for (int j = 0;; j++)
   {
    if (array[key[i]][j] != '\0')
     cout << array[key[i]][j];
    else
     break;
   }
  }
  
  //for (int i = 0; i < row; i++) // for test
  //{
  // for (int j = 0; j < row; j++)
  //  cout << array[i][j];
  // cout << endl;
  //}
  cout << endl;
 }
 return 0;
}

3.3-PlayfairCipher-Lab

解題思路:
其實照著題目步驟一步步寫就好了，只要不要會錯意應該就沒有大問題。

程式碼:

#include <iostream>
#include <string>
using namespace std;
void findPosition(char c,char table[5][5],int &x,int &y)
{
 for (int i = 0; i < 5; i++)
 {
  for (int j = 0; j < 5; j++)
  {
   if (c == table[i][j])
   {
    x = i, y = j;
    return;
   }
  }
 }
}

int main() {
 string plaintext, key;
 
 while (cin >> plaintext >> key)
 {
  char table[5][5] = {'\0'};
  int alphabetIndex[26] = { 0 }; // check if alphabet is recorded in table
  alphabetIndex['j' - 'a'] = 1; // aviod error
  int currentRow = 0, currentColumn = 0, currentPoint = 0; // current recorded position
  string answer = "";
  for (int i = 0; i < key.size(); i++)
  {
   if (alphabetIndex[key[i] - 'a'] == 0) // if new
   {
    table[currentRow][currentColumn] = key[i];
    currentColumn++;
    if (currentColumn >= 5) // next line
    {
     currentColumn %= 5;
     currentRow++;
    }
   }
   if (key[i] == 'j' && alphabetIndex['i' - 'a'] == 0) // 'j' case
   {
    table[currentRow][currentColumn] = 'i';
    currentColumn++;
    if (currentColumn >= 5) // next line
    {
     currentColumn %= 5;
     currentRow++;
    }
    alphabetIndex['i' - 'a']++;
   }
   alphabetIndex[key[i] - 'a']++; // increase index record
  }
  for (int i = 0; i < 26; i++) //fill the table
  {
   if (alphabetIndex[i] == 0)
   {
    table[currentRow][currentColumn] = (i + 'a');
    currentColumn++;
    if (currentColumn >= 5) // next line
    {
     currentColumn %= 5;
     currentRow++;
    }
   }
  }
  while (currentPoint <= plaintext.size() - 1) // encode
  {
   int c1Row = 0, c1Column = 0, c2Row = 0, c2Column = 0;
   if (currentPoint == plaintext.size()-1)
   {
    findPosition(plaintext[currentPoint], table, c1Row, c1Column);
    findPosition('x', table, c2Row, c2Column);
    currentPoint++;
   }
   else if (plaintext[currentPoint] != plaintext[currentPoint + 1]) // they are different
   {
    findPosition(plaintext[currentPoint], table, c1Row, c1Column);
    findPosition(plaintext[currentPoint + 1], table, c2Row, c2Column);
    currentPoint += 2; // to the next point
   }
   else
   {
    findPosition(plaintext[currentPoint], table, c1Row, c1Column);
    findPosition('x', table, c2Row, c2Column);
    currentPoint += 1;
   }

   if (c1Row == c2Row)
   {
    answer += table[c1Row][(c1Column + 1) % 5];
    answer += table[c2Row][(c2Column + 1) % 5];
   }
   else if (c1Column == c2Column)
   {
    answer += table[(c1Row + 1) % 5][c1Column];
    answer += table[(c2Row + 1) % 5][c2Column];
   }
   else
   {
    answer += table[c1Row][c2Column];
    answer += table[c2Row][c1Column];
   }
  }
  cout << answer << endl;
  //for (int i = 0; i < 5; i++) // print table
  //{
  // for (int j = 0; j < 5; j++)
  //  cout << table[i][j];
  // cout << endl;
  //}
 }
    return 0;
}

#讀報 Taiwan Has Been Shut Out of Global Health Discussions. Its Participation Could Have Saved Lives

新聞網址

by chance :偶然
out in the cold :冷落
came to power:上台
muddied the waters:攪混水
be out of the woods:脫離困境
hoarding:囤貨

"China muddied the waters of geopolitics and global health – and today we see the consequences."

2.1-Computes the average and standard deviation

程式碼:
解法一:

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
 int n;
 double total = 0, m, sd = 0, num;
 vector<double> si;
 while (cin >> n)
 {
  total = sd = 0;
  for (int i = 0; i < n; i++)
  {
   cin >> num;
   si.push_back(num);
   total += num;
  }
  m = total / n;
  cout << "Average:" << m;
  for (int i = 0; i < n; i++)
  {
   sd += pow((si[i] - m), 2);
  }
  sd = sqrt(sd / n);
  cout << "\t" << "Standard deviation:" << sd << endl;
  si.clear();
 }


 return 0;
}

解法二

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        double *arr=new double[n];
        double average=0,deviation=0;
        for(int i=0;i<n;i++)
        {
            cin>>arr[i];     
            average+=arr[i];
        }
        average/=n;
        for(int i=0;i<n;i++)
        {
            deviation+=(arr[i]-average)*(arr[i]-average);
        }
        deviation=sqrt(deviation/n);
        cout << "Average:" << average << "\t" << "Standard deviation:" << deviation << endl;
    }
    return 0;
}

2.3-Square Code

解題心得:
輸入資料後，首先要找出方塊的長跟寬。我想像中一開始就單純一行，然後有個可移動的直線控制一行的數量，一次往內縮減一格，直到符合條件才停止。
其中

width = len / height + (len % height ? 1 : 0);

這行是看看長度除以高度能否被整除?如果不能，代表說有不成行的，要加一。
最後就是輸出答案。
程式碼:

#include <iostream>
#include <string>
using namespace std;

int main()
{
 int len, width, height; //height >= width
 string s;
 while (cin >> s)
 {
  len = s.size();
  height = 1;
  width = len / height;
  while (width > height) // find height & width
  {
   height++;
   width = len / height + (len % height ? 1 : 0); //make sure width is right
  }
  for (int i = 0; i < height; i++) // print squre
  {
   for (int j = 0; j < width; j++)
   {
    if (i + j * height < len)
     cout << s[i + j * height];
    else
     cout << " ";
   }

   cout << endl;
  }
 }
 return 0;
}

另一個解法

#include <iostream>
#include <string>
using namespace std;

int main() {
 string text;
 while (cin >> text)
 {
  int n = 1;
  while (n*n < text.size())
   n++;
  if (n*n == text.size())
  {
   for (int i = 0; i < n; i++)
   {
    for (int j = 0; j < n; j++)
     cout << text[i + n * j];
    cout << endl;
   }
  }
  else
  {
   int w = text.size() % n == 0 ? text.size() / n : text.size() / n + 1;
   for (int i = 0; i < n; i++)
   {
    for (int j = 0; j < w; j++)
    {
     if (i + n * j >= text.size())
      cout << " ";
     else
      cout << text[i + n * j];
    }

    cout << endl;
   }
  }
 }
    return 0;
}

2.2-Leaderboard

解題心得:
使用vector動態紀錄資料，全部輸入後使用getHighScores函數三次，此函數每次會找到該次最大值，輸出後把該質歸零。

程式碼:

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

void getHighScores(vector<string> &names, vector<int> &scores)
{
 int maxScore = 0, mark = 0, i;
 for (i = 0; i < scores.size(); i++)
 {
  if (scores[i] > maxScore)
  {
   maxScore = scores[i];
   mark = i;
  }
 }
 cout << names[mark] << endl;
 cout << maxScore << endl;
 scores[mark] = 0;
}

int main()
{
 //fstream file;
 //file.open("scores.txt", ios::in);
 vector<int> scores;
 vector<string> names;
 string temp_name;
 int temp_score;
 while (cin >> temp_name >> temp_score) //read file
 {
  names.push_back(temp_name);
  scores.push_back(temp_score);

 }
 getHighScores(names, scores);
 getHighScores(names, scores);
 getHighScores(names, scores);
 //file.close();
 return 0;
}

1.3-Compute_Sphere_Volume-lab

程式碼:

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
 const double PI = 3.14159265358979323846;
 double r,volume;
 while (cin >> r)
 {
  volume = 4.0 / 3.0 * PI * r * r * r;
  cout << fixed << setprecision(6) << volume << endl;
 }
    return 0;
}

1.2-Input_Output.docx

解題心得:
那時候不知道中了甚麼邪，要這樣寫，明明可以用setw().......
解法二是剛剛寫的，沒有丟judge不過應該也對。

程式碼:
(解法一)

#include <iostream>
#include <string>
#include <iomanip>
using namespace std;

int main() {
 string s;
 int len;
 while (cin >> s)
 {
  len = s.size();
  if (len < 10)
  {
   for (int i = 0; i < 10 - len; i++)
    cout << " ";
   cout << s << endl;
  }
  else if(len >= 10)
   cout << s << endl;
 }
    return 0;
}

(解法二)

#include <iostream>
#include <iomanip>
#include <string>
using namespace std;

int main()
{
    string number;
    while(cin >> number)
    {
        if(number.size() < 10)
            cout << setw(10) << number << endl;
        else
            cout << number << endl;
    }
    return 0;
}

1.1-Pattern_Output-lab

程式碼:

#include <iostream>
using namespace std;

int main() {
 cout << "       *" << endl;
 cout << "      *" << endl;
 cout << "     *" << endl;
 cout << "*   *" << endl;
 cout << " * *" << endl;
 cout << "  *" << endl;
    return 0;
}

3.2-Text-based histogram

解題心得:
簡單題。

程式碼:

#include <iostream>
using namespace std;

int main()
{
 const int SCALE = 6;
 int grade, studentGrades[SCALE] = { 0 };
 while (cin >> grade) // record inputs
 {
  studentGrades[grade]++;
 }
 for (int i = 0; i < SCALE; i++)
 {
  cout << studentGrades[i] << " grade(s) of " << i << endl;
 }
 return 0;
}

3.1-Occurrenc Counting

解題心得:
開兩個陣列，一個紀錄數字，一個紀錄該數字出現次數。
每當有新的輸入時，就找一次當前紀錄陣列，如果已被記錄過就出現次數加一，沒有則放到最後面。
最後，從數字最大的開始輸出，輸出後把該數出現次數歸零，且把紀錄最大值的變數重設數質(不設零是因為有小於零的數)

程式碼:

#include <iostream>
using namespace std;

int main()
{
 int number[100] = { 0 }, times[100] = { 0 };
 int n, flag = 0, check, maxNumber = -100000; // flag records current array's length 

 while (cin >> n)
 {
  check = 0; // check if this number has been recorded
  for (int i = 0; i < flag; i++)
  {
   if (n == number[i])
   {
    times[i]++;
    check = 1;
    break;
   }
  }
  if (check == 0) // if number is new
  {
   number[flag] = n;
   times[flag]++;
   flag++;
  }

  if (n > maxNumber) // find max number
   maxNumber = n;
 }

 cout << "N\tcount" << endl;
 for (int i = 0; i < flag; i++)
 {
  for (int j = 0; j < flag; j++)
  {
   if (number[j] == maxNumber)
   {
    cout << number[j] << "\t" << times[j] << endl;
    times[j] = 0;
    maxNumber = -100000;
   }

   for (int k = 0; k < flag; k++)
   {
    if (number[k] > maxNumber && times[k] != 0)
     maxNumber = number[k];
   }
  }

 }

 return 0;
}

另解

#include <iostream>
using namespace std;

int main() {
 int n, arr[100], len = 0, occur[100] = { 0 };
 while (cin >> n)
 {
  int not_occur = 1;
  for (int i = 0; i < len; i++)
  {
   if (n == arr[i])
   {
    occur[i]++;
    not_occur = 0;
    break;
   }
  }
  if (not_occur)
  {
   arr[len] = n;
   occur[len]++;
   len++;
  }
 }
 for (int i = 0; i < len; i++)
 {
  for (int j = 0; j < len; j++)
  {
   if (arr[i] > arr[j])
   {
    swap(arr[i], arr[j]);
    swap(occur[i], occur[j]);
   }
  }
 }
 cout << "N\tcount" << endl;
 for (int i = 0; i < len; i++)
 {
  cout << arr[i] << "\t" << occur[i] << endl;
 }
    return 0;
}

2.3-Compute_The_Tax - lab

解題心得:
快樂簡單題~不過一開始不知為何有誤差，但多丟幾次就莫名其妙過了

程式碼:

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
 float income,tax;
 while (cin >> income)
 {
  if (income < 750)
   tax = income * 0.01;
  else if (income <= 2250)
   tax = 7.50 + (income - 750) * 0.02;
  else if (income <= 3750)
   tax = 37.50 + (income - 2250) * 0.03;
  else if (income <= 5250)
   tax = 82.50 + (income - 3750) * 0.04;
  else if (income <= 7000)
   tax = 142.50 + (income - 5250) * 0.05;
  else
   tax = 230.00 + (income - 7000) * 0.06;
  //tax += 1e-6;
  cout << fixed << setprecision(2) << tax << endl;
 }
    return 0;
}

2.2-Adding_Large_Numbers - lab

解題心得:
其實不是很了解為啥規定用struct寫。這題本質就是大數運算。
我add function因為怕時間內做不完當時是先拿下面網址的code改來用，之後有空應該會重新寫一次......
reference:How to get the sum of two strings of numbers - C++

程式碼:

#include <iostream>
#include <string>
using namespace std;

struct BigInt
{
 string numberArray;
 int length;
};
BigInt Add(const BigInt &na, const BigInt &nb)
{
 string a = na.numberArray, b = nb.numberArray;
 if (a.size() < b.size()) // make sure a is always longer.
  swap(a, b);
 int j = a.size() - 1;
 for (int i = b.size() - 1; i >= 0; i--, j--) // 從個位數開始相加
  a[j] += (b[i] - '0');

 for (int i = a.size() - 1; i > 0; i--)
 {
  if (a[i] > '9') // make sure each digit is smaller than 10
  {
   int d = a[i] - '0';
   a[i - 1] = ((a[i - 1] - '0') + d / 10) + '0';
   a[i] = (d % 10) + '0';
  }
 }
 if (a[0] > '9') // 如果最高位需要進位的處理
 {
  string k;
  k += a[0];
  a[0] = ((a[0] - '0') % 10) + '0'; // 取個位數
  k[0] = ((k[0] - '0') / 10) + '0'; // 取十位數
  a = k + a; // append
 }
 BigInt result;
 result.numberArray = a;
 return result;
  
 
}
int checkInput(string &number)
{
 int check = 0;// if check is 1, then it is invalid input.
 for (int i = 0; i < number.size(); i++)
 {
  if (!isdigit(number[i]))
  {
   return 1;
  }
 }
 return 0;
}
int main() {
 BigInt a, b, result;
 string n1, n2;
 int n;
 while (cin >> n)
 {
  for (int i = 0; i < n; i++) // input data
  {
   cin >> n1 >> n2;
   if (checkInput(n1) || checkInput(n2))
   {
    cout << "Not a valid number, please try again." << endl;
    continue;
   }
   a.numberArray = n1;
   a.length = n1.size();
   b.numberArray = n2;
   b.length = n2.size();
   result = Add(a, b);
   cout << result.numberArray << endl;
  }
 }
    return 0;
}

補上自己重寫一遍的程式碼

#include <iostream>
#include <string>
using namespace std;

struct BigInt
{
 string number;
};

BigInt add(BigInt &a, BigInt &b)
{
 string n1 = a.number, n2 = b.number;
 if (n1.size() < n2.size())
  swap(n1, n2);
 int len1 = n1.size(), len2 = n2.size(), j = len1-1; // j is bottom index of n1

 for (int i = len2-1; i >= 0; i--, j--) // 把n2先直接加上n1
 {
  n1[j] += (n2[i] - '0');
 }
 for (int i = len1 - 1; i > 0; i--) // 除了 index 0 ,其餘都檢查是否需要進位
 {
  if (n1[i] > '9')
  {
   n1[i] = (n1[i] - '0') % 10 + '0';
   n1[i - 1] += 1;
  }
 }

 if (n1[0] > '9')
 {
  string append = "1";
  n1[0] = (n1[0] - '0') % 10 + '0';
  append = append + n1;
  n1 = append;
 }
 BigInt result;
 result.number = n1;
 return result;
}

int checkInput(string numberArray)
{
 for (int i = 0; i < numberArray.size(); i++)
 {
  if (!isdigit(numberArray[i]))
   return 0;
 }
 return 1;
}
int main()
{
 BigInt a, b;
 while (cin >> a.number >> b.number)
 {
  if (checkInput(a.number) && checkInput(b.number))
  {
   BigInt result = add(a, b);
   cout << result.number << endl;
  }
  else
   cout << "Not a valid number, please try again." << endl;
 }
 
 return 0;
}

2.1-Print_Standard_Format - lab

解題心得:
資料可分為三類，分別為名字、薪水、獎金。雖然後兩者實際上為數字，不過直接當字串處理比較方便。
在使用迴圈讀取資料時，就分別用三個變數紀錄最長長度。
話說同學用vector，知道我直接開三個長度1000的array吐槽說解法很暴力XD

字串固定長度使用: setw(n)
數字設定精度使用:fixed << setprecision(n) << string


程式碼:

#include <iostream>
#include <iomanip>
#include <string>
using namespace std;

int main() {
 int n;
 string names[1000], salary[1000], award[1000];
 while (cin >> n)
 {
  int nameLength = 0, salaryLength = 0, awardLength = 0;
  for (int i = 0; i < n; i++)
  {
   cin >> names[i] >> salary[i] >> award[i];
   if (names[i].size() > nameLength)
    nameLength = names[i].size();
   if (salary[i].size() > salaryLength)
    salaryLength = salary[i].size();
   if (award[i].size() > awardLength)
    awardLength = award[i].size();
  }
  for (int i = 0; i < n; i++)
  {
   cout << setw(nameLength) << names[i] << "|  "
    << setw(salaryLength) << salary[i] << "|  "
    << setw(awardLength) << award[i] << endl;
  }
  
 }
    return 0;
}

11398 - The Base-1 Number System

先說這個解法在uva給我CE.....我的想法是一次讀一行做分析，不過比較好的好像是一個區段一個區段計算就好。

程式碼:(解法一)

#include <stdio.h>

int main()
{
    char s[1000];
    while(gets(s)!=0&&s[0]!='~')
    {
        int i=0,num=0,flag=0,n=0;
        while(s[i]!='#')
        {
            if(s[i+1]==' ')
            {
                i+=2;
                flag=1;
            }
            else if(s[i+2]==' ')
            {
                i+=3;
                flag=0;
            }
            while(s[i]!=' ')
            {
                i++;
                n++;
            }
            i++;
            for(int j=0;j<n-2;j++)
                num=num*2+flag;
            n=0;
        }
        printf("%d\n",num);
    }

    return 0;
}

下面這個丟兩邊都有過，而且想法簡單多了，真不知我為什麼沒想到。
程式碼:(解法二)

#include <stdio.h>
#include <string.h>
int main()
{
    int flag=0,num=0,n;
    char s[31];
    while(scanf("%s",s)&&s[0]!='~')
    {

        if(s[0]=='#')
        {
            printf("%d\n",num);
            num=0;
        }
        else if(strlen(s)==1)
        {
            flag=1;
        }
        else if(strlen(s)==2)
        {
            flag=0;
        }
        else
        {
            n=strlen(s)-2;
            for(int i=0;i<n;i++)
                num=num*2+flag;
        }
    }

    return 0;
}

11462－Age Sort

丟uva好幾次才過，Presentation error害死我......

程式碼:

#include <stdio.h>

int main()
{
    int n,age[101]={0},temp;
    while(scanf("%d",&n))
    {
        for(int i=0;i<101;i++)
            age[i]=0;
        if(n==0)
            break;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&temp);
            age[temp]++;
        }
        int block=0;
        for(int i=0;i<101;i++)
        {
            while(age[i]>0)
            {
                if(block) printf(" ");
                block++;
                printf("%d",i);
                age[i]--;
            }
        }
        printf("\n");
    }
    
    return 0;
}