「AOJ再挑戦問5～9」の編集履歴（バックアップ）一覧はこちら
「AOJ再挑戦問5～9」(2014/01/11 (土) 04:24:07) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*問5 GCD and LCM
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0005&lang=jp
2つの整数の最小公倍数と最大公約数を出力する問題。
**解法
公式通りgcdとlcmを計算するだけです。
#include<stdio.h>
int gcd ( int a, int b ){
int c;
while ( a != 0 ) {
c = a; a = b%a; b = c;
}
return b;
}
int main(){
int g,a,b;
while(scanf("%d %d",&a,&b)!=EOF){
g=gcd(a,b);
printf("%d %d\n",g,a*(b/g));
}
}
*問6 Reverse Sequence
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0006&lang=jp
読み込んだ文字列を逆順に表示するプログラムをかけ。
**解法
文字列を逆順に表示するだけです。
#include<stdio.h>
#include <string.h>
int main(){
char str[21];
scanf("%s",str);
for(int i=strlen(str)-1;i>=0;i--)printf("%c",str[i]);
printf("\n");
}
*問7 Debt Hell
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0007
複利借金の額を計算する問題。
解法
整数型で計算しても問題ありません。
1000以下があれば自動で切り上げるだけです。
#include<stdio.h>
int main(){
int n,m=100000;
scanf("%d",&n);
while(n--){
m*=1.05;
if(m%1000>0){
m+=1000-(m%1000);
}
}
printf("%d\n",m);
}
*問8 Sum of 4 Integers
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0008&lang=jp
0～9の数を4つ足してできる数字の作り方の組み合わせ数を求める問題。
解法
最初に全部の場合の答えを初歩的な動的計画法で求めます。
計算量は大差ないので4重ループで求めてもよいでしょう。
#include<stdio.h>
int main(){
int ans[51]={0},n;
ans[0]=1;
for(int i=0;i<4;i++){
for(int k=36;k>=0;k--){
for(int j=1;j<=9 && k-j>=0;j++){
ans[k]+=ans[k-j];
}
}
}
while(scanf("%d",&n)!=EOF){
printf("%d\n",ans[n]);
}
}
*問9 Prime Number
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0009&lang=jp
指定された数ｎ以下の素数の個数をこたえる問題。
解法
篩で選り分けてあとは下からカウントするだけです。
count配列のメモリ使用量がもったいない感じですがあまり気にしません。
*問5 GCD and LCM
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0005&lang=jp
2つの整数の最小公倍数と最大公約数を出力する問題。
**解法
公式通りgcdとlcmを計算するだけです。
#include<stdio.h>
int gcd ( int a, int b ){
int c;
while ( a != 0 ) {
c = a; a = b%a; b = c;
}
return b;
}
int main(){
int g,a,b;
while(scanf("%d %d",&a,&b)!=EOF){
g=gcd(a,b);
printf("%d %d\n",g,a*(b/g));
}
}
*問6 Reverse Sequence
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0006&lang=jp
読み込んだ文字列を逆順に表示するプログラムをかけ。
**解法
文字列を逆順に表示するだけです。
#include<stdio.h>
#include <string.h>
int main(){
char str[21];
scanf("%s",str);
for(int i=strlen(str)-1;i>=0;i--)printf("%c",str[i]);
printf("\n");
}
*問7 Debt Hell
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0007
複利借金の額を計算する問題。
解法
整数型で計算しても問題ありません。
1000以下があれば自動で切り上げるだけです。
#include<stdio.h>
int main(){
int n,m=100000;
scanf("%d",&n);
while(n--){
m*=1.05;
if(m%1000>0){
m+=1000-(m%1000);
}
}
printf("%d\n",m);
}
*問8 Sum of 4 Integers
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0008&lang=jp
0～9の数を4つ足してできる数字の作り方の組み合わせ数を求める問題。
解法
最初に全部の場合の答えを初歩的な動的計画法で求めます。
計算量は大差ないので4重ループで求めてもよいでしょう。
#include<stdio.h>
int main(){
int ans[51]={0},n;
ans[0]=1;
for(int i=0;i<4;i++){
for(int k=36;k>=0;k--){
for(int j=1;j<=9 && k-j>=0;j++){
ans[k]+=ans[k-j];
}
}
}
while(scanf("%d",&n)!=EOF){
printf("%d\n",ans[n]);
}
}
*問9 Prime Number
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0009&lang=jp
指定された数ｎ以下の素数の個数をこたえる問題。
解法
篩で選り分けてあとは下からカウントするだけです。
count配列のメモリ使用量がもったいない感じですがあまり気にしません。
#include<stdio.h>
#include<math.h>
#include<string.h>
const int limit=1000001;
bool is_prime[limit];
int count[limit]={0};
void calc(){
//エラトステネスの篩
memset(is_prime,true,sizeof(is_prime));
is_prime[0]=is_prime[1]=false;
for(int i=2;i<=sqrt(limit);i++){
if(is_prime[i]==false)continue;
for(int j=i*2;j<limit;j+=i){
is_prime[j]=false;
}
}
//素数の個数のカウント
for(int i=1;i<limit;i++){
count[i]=count[i-1]+is_prime[i];
}
}
int main(){
int n;
calc();
while(scanf("%d",&n)!=EOF){
printf("%d\n",count[n]);
}
}
