としおの読書生活

田舎に住む社会人の読書記録を綴ります。 主に小説や新書の内容紹介と感想を書きます。 読書の他にもワイン、紅茶、パソコン関係などの趣味を詰め込んだブログにしたいです。

カテゴリ： 競技プログラミング

C++でStackを使用して逆ポーランド記法で入力された式の結果を求めるというAIZU ONLINE JUDGEのALDS_1_3_Aを解きました。


【目次】
逆ポーランド記法とは
問題
Stackの実装




逆ポーランド記法とは


逆ポーランド記法とは、演算子をオペランドの後に記述するプログラムを記述する記法です。

例えば、(1 + 2) * (5 + 4)という中間記法で書かれた数式があったとする。

これを逆ポーランド記法では次のように書くことができます。

1 2 + 5 4 + *



問題


逆ポーランド記法で与えられた数式の計算結果を出力してください。

入力例


１つの数式が１行に与えられます。連続するシンボル（オペランドあるいは演算子）は１つの空白で区切られて与えられます。
1 2 +


出力例


計算結果を１行に出力してください。

3

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/3/ALDS1_3_Aより



Stackの実装


#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

using namespace std;

struct Stack{
int S[1000];
int Top;
};

void push(Stack* stack, int num){
stack->S[stack->Top] = num;
stack->Top++;
}

int pop(Stack *stack){
stack->Top--;
return stack->S[stack->Top];
}

int main(void){
Stack stStack = {0};
char s[100];
int num1, num2;
while(scanf("%s", s) != EOF){
if (s[0] == '+'){
num1 = pop(&stStack);
num2 = pop(&stStack);
push(&stStack, num2+num1);
}
else if(s[0] == '-'){
num1 = pop(&stStack);
num2 = pop(&stStack);
push(&stStack, num2-num1);
}
else if(s[0] == '*'){
num1 = pop(&stStack);
num2 = pop(&stStack);
push(&stStack, num2*num1);
}
else{
push(&stStack, atoi(s));
}
}

num1 = pop(&stStack);
cout << num1 << endl;

return 0;
}




タグ ：
#C++
#競技プログラミング
#データ構造
コメント（0）

C++でバブルソートの問題であるAIZU ONLINE JUDGEのALDS_1_2_Dを解きました。


【目次】
問題
シェルソートを実装する




問題


1  insertionSort(A, n, g)
2      for i = g to n-1
3          v = A[i]
4          j = i - g
5          while j >= 0 && A[j] > v
6              A[j+g] = A[j]
7              j = j - g
8              cnt++
9          A[j+g] = v
10
11 shellSort(A, n)
12     cnt = 0
13     m = ?
14     G[] = {?, ?,..., ?}
15     for i = 0 to m-1
16         insertionSort(A, n, G[i])

shellSort(A, n) は、一定の間隔 gg だけ離れた要素のみを対象とした挿入ソートである insertionSort(A, n, g) を、最初は大きい値から gg を狭めながら繰り返します。これをシェルソートと言います。

上の疑似コードの ? を埋めてこのプログラムを完成させてください。nn と数列 AA が与えられるので、疑似コード中の mm、mm 個の整数 Gi(i=0,1,...,m−1)Gi(i=0,1,...,m−1)、入力 AAを昇順にした列を出力するプログラムを作成してください。




シェルソートを実装する


ソートを行う間隔gは最後が1で終わればどんな数列でも良さそうだったので今回は、gn+1 = 3gn + 1という数列を使用します。

この数列に2のべき乗のような間隔が短すぎるものを入れると無駄な計算が発生しやすくなり、
シェルソートで実装する意味がなくなるみたいです。

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int cnt = 0;

void insertionSort(int *A, int n, int g){
for(int i=g; i<n; ++i){
int v = A[i];
int j = i-g;
while ((j >= 0) && (A[j] > v)){
A[j+g] = A[j];
j = j - g;
cnt++;
}
A[j+g] = v;
}
}

void shellSort(int* A, int n){
cnt = 0;
int m = 1;
vector<int> G;
G.push_back(1);
while(3*G[m-1]+1 <= n){
G.push_back(3*G[m-1]+1);
m++;
}

cout << m << endl;
for(int i=G.size()-1;i>=0; --i){
cout << G[i];
if (i != 0){
cout << " ";
}
}
cout << endl;

for(int i = G.size()-1; i >= 0; --i){
insertionSort(A, n, G[i]);
}
}

int main(void){
int n;
cin >> n;
int *A = new int[n];
for(int i=0; i<n; ++i){
cin >> A[i];
}
shellSort(A, n);
cout << cnt << endl;
for(int i=0; i<n; ++i){
cout << A[i] << endl;
}

return 0;
}
タグ ：
#C++
#競技プログラミング
#アルゴリズム
コメント（0）

C++でバブルソートの問題であるAIZU ONLINE JUDGEのALDS_1_2_Aを解きました。


【目次】
問題
バブルソートを実装する




問題


数列 A を読み込み、バブルソートで昇順に並び変え出力するプログラムを作成してください。また、バブルソートで行われた要素の交換回数も報告してください。


入力例


入力の最初の行に、数列の長さを表す整数 N が与えられます。２行目に、N 個の整数が空白区切りで与えられます。

5
5 3 2 4 1


出力例


出力は 2 行からなります。１行目に整列された数列を 1 行に出力してください。数列の連続する要素は１つの空白で区切って出力してください。2 行目に交換回数を出力してください。
1 2 3 4 5
8

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_2_Aより



バブルソートを実装する


#include <iostream>
#include <cmath>

using namespace std;

void bubbleSort(int *A, int n){
int count = 0;
int flag = 1;
while(flag){
flag = 0;
for(int i=n-1; i>=0; --i){
if (A[i] < A[i-1]){
swap(A[i], A[i-1]);
count++;
flag = 1;
}
}
}
for(int i=0; i<n-1; ++i){
cout << A[i] << " ";
}
cout << A[n-1] << endl;
cout << count << endl;
}

int main(void){
int n;
cin >> n;
int* A = new int[n];
for (int i=0; i<n; ++i){
cin >> A[i];
}
bubbleSort(A, n);
delete[] A;
return 0;
}


タグ ：
#C++
#競技プログラミング
#アルゴリズム
コメント（0）

C++で選択ソートの問題であるAIZU ONLINE JUDGEのALDS_1_2_Bを解きました。


【目次】
問題
選択ソートの実装




問題


数列Aを読み込み、選択ソートのアルゴリズムで昇順に並び替え出力するプログラムを作成してください。


入力例


入力の最初の行に、数列の長さを表す整数 N が与えられます。２行目に、N 個の整数が空白区切りで与えられます。
6
5 6 4 2 1 3


出力例


出力は 2 行からなります。１行目に整列された数列を 1 行に出力してください。数列の連続する要素は１つの空白で区切って出力してください。2 行目に交換回数を出力してください。
1 2 3 4 5 6
4

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_2_Bより



選択ソートの実装


#include <iostream>
#include <cmath>

using namespace std;

void selectSort(int *A, int n){
int count = 0;
for(int i=0; i<n; ++i){
int minj = i;
for(int j=i; j<n; ++j){
if (A[j] < A[minj]){
minj = j;
}
}
if (i != minj){
swap(A[i], A[minj]);
count++;
}
}
for(int i=0; i<n-1; ++i){
cout << A[i] << " ";
}
cout << A[n-1] << endl;
cout << count << endl;
}

int main(void){
int n;
cin >> n;
int* A = new int[n];
for (int i=0; i<n; ++i){
cin >> A[i];
}
selectSort(A, n);
delete[] A;
return 0;
}



タグ ：
#C++
#競技プログラミング
#アルゴリズム
コメント（0）

C++で挿入ソートの問題であるAIZU ONLINE JUDGEのALDS_1_1_Aを解きました。


【目次】
問題概要
挿入ソートの実装




問題概要


N 個の要素を含む数列 A を昇順に並び替える挿入ソートのプログラムを作成してください。


入力例
6
5 2 4 6 1 3

出力例
5 2 4 6 1 3
2 5 4 6 1 3
2 4 5 6 1 3
2 4 5 6 1 3
1 2 4 5 6 3
1 2 3 4 5 6

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_Aより



挿入ソートの実装


#include <iostream>

using namespace std;

void insertSort(int* A, int n){
for(int i=0; i<n; ++i){
int v = A[i];
int j = i - 1;
while((j >= 0) && (A[j] > v)){
A[j+1] = A[j];
j--;
}
A[j+1] = v;

// 結果出力
for(int i=0; i<n-1; ++i){
cout << A[i] << " ";
}
cout << A[n-1] << endl;
}
}

int main(void){
int n;
cin >> n;
int *nums = new int[n];
for (int i=0; i<n; ++i){
cin >> nums[i];
}
insertSort(nums, n);
return 0;
}


タグ ：
#C++
#競技プログラミング
#アルゴリズム
コメント（0）

↑このページのトップヘ