一歩ずつアルゴリズムを勉強します.
8217 ワード
私は大学二年生で、最近アルゴリズムを独学し始めました.ここで自分の学習過程で接触した問題を記録します.君と励まし合う
水のレベルが限られています.現在のテーマは水と比較します.
テーマ分布は5＋1です 5自分で勉強する5つの水の問題です.1はネットで見つけた比較的にレベルのあるテーマです.
一歩ずつアルゴリズムを勉強します.
窮挙法
計算方法を挙げるのはプログラム設計の中で最も普遍的に使われています.みんなは熟練して正確に運用するアルゴリズムを身につけなければなりません.コンピュータの演算速度が速く、精度が高いという特徴を利用して、問題を解決するあらゆる可能性のある状況に対して、漏れなく検査を行い、その中から要求に合った答えを探し出す.
貧しいアルゴリズムで問題を解決すると、通常二つの面から分析ができます.
一、問題に関わる状況:問題に関わる状況は何がありますか?状況の種類は確定できません.それを説明してください.
答えは満足の条件が必要です.分析されたこれらの状況は、どのような条件を満たす必要がありますか?これらの条件を述べなさい.
1.株当たり数
問題の説明:
プログラムを作成して、100以内のすべての株価を求めます.
問題の分析:
Iは斜辺(0(=i〈100〉、j、mは直角辺(j、k〈i)であり、条件を満たすすべてのi、j値時mの値を二重循環で求め、mは斜辺iよりも小さい完全な二乗数であるか否かを判断し、その条件を満たすと、記数変数nに1を加算する.
2.親密数
問題の説明:
10000以内の親密数を求めます.親密数:Aの因子とBの場合、Bの因子とAの場合、AとBは親密数です.
Aの因子を整えています.Aの正の整数を全部取り除きます.12のような因子は、1、2、3、4、5、6です.
問題の分析:
単なる遍歴にすぎません.1000以内の条件を満たすすべての親密数を検索します.本題は求める数の因子と、その複雑さを減らすための関数を使用します.
3.正方形の定理
問題の説明:
プログラミング検証「正方定理」:いずれの自然数も四つの数の平方和によって表現できます.
問題の分析:
このような問題の最も主要なのは循環変数の開始と終了を考慮して値を取ることです.このプログラムには4サイクルが使われています.実は3サイクルだけでこの問題を解決できます.試してみてください.
4、百元問題
問題の説明:
王おばさんは100元で100頭の小さい家畜を買います.多くは「百元」を要求していません.子牛は頭10元で、子羊は一匹3元で、うさぎは0.5元です.彼女の代わりにどうやって買うべきですか?
問題の分析:
変数i,jでそれぞれ牛、羊の頭の数を表します.牛を買うにはI*10元、羊を買うにはi*3元が必要です.この時、残りのお金と残りのお金を計算してウサギの頭の数を買うことができます.3種類の小家畜の総頭数によって解を求めることができます.
5.連続と数
問題の説明:
十三個の連続の自然数を探してください.全部合数です.
問題の分析:
「合数」とは、素数ではなく、次の解法は合数の印としてflagsを使い、カウントします.
6*貧乏なやり方で0—1リュックサックの問題を解決します.
問題の説明:
選択したものの総重量は指定の制限重量を超えないようにします.ただし、選択したものの価値は最大です.
問題の分析:
n個の物品の重さと価値をそれぞれ保存に設定して配列w[]とv[]の中で、制限重量はtwです.一つのn元グループ(x 0,x 1,…,xn-1)を考慮します.このうち、xi=0はi番目のものが選択されていないことを示していますが、xi=1はi番目のものが選択されていることを示しています.エニュメレーションでリュックサックの問題を解決するには、すべての選択肢を列挙する必要があります.
各成分の取得値は0または1のn元グループの個数は2 n個であることは明らかであるが、各n元グループは実際には1つの長さnの2進数に対応しており、これらの2進数の取得範囲は0〜2 n−1である.したがって、0〜2 n−1をそれぞれ対応する2進数に変換すれば、必要な2 n個のn元グループを得ることができる.
水のレベルが限られています.現在のテーマは水と比較します.
テーマ分布は5＋1です 5自分で勉強する5つの水の問題です.1はネットで見つけた比較的にレベルのあるテーマです.
一歩ずつアルゴリズムを勉強します.
窮挙法
計算方法を挙げるのはプログラム設計の中で最も普遍的に使われています.みんなは熟練して正確に運用するアルゴリズムを身につけなければなりません.コンピュータの演算速度が速く、精度が高いという特徴を利用して、問題を解決するあらゆる可能性のある状況に対して、漏れなく検査を行い、その中から要求に合った答えを探し出す.
貧しいアルゴリズムで問題を解決すると、通常二つの面から分析ができます.
一、問題に関わる状況:問題に関わる状況は何がありますか?状況の種類は確定できません.それを説明してください.
答えは満足の条件が必要です.分析されたこれらの状況は、どのような条件を満たす必要がありますか?これらの条件を述べなさい.
1.株当たり数
問題の説明:
プログラムを作成して、100以内のすべての株価を求めます.
問題の分析:
Iは斜辺(0(=i〈100〉、j、mは直角辺(j、k〈i)であり、条件を満たすすべてのi、j値時mの値を二重循環で求め、mは斜辺iよりも小さい完全な二乗数であるか否かを判断し、その条件を満たすと、記数変数nに1を加算する.
#include <stdio.h>
#include <math.h>
int main()
{
int i, j, k, n = 1;
for (i=1; i<100; i++)
{
for (j=1; j<i; j++)
{
k = sqrt(i*i-j*j);
if ((k*k == i*i-j*j) && (k <= j))
{
printf("%d : %d,%d,%d
", n++, i, j, k);
}
}
}
return 0;
}
/**********************************
：
1 : 5,4,3
2 : 10,8,6
3 : 13,12,5
4 : 15,12,9
5 : 17,15,8
。。。。。。。。。。。。。
**********************************/2.親密数
問題の説明:
10000以内の親密数を求めます.親密数:Aの因子とBの場合、Bの因子とAの場合、AとBは親密数です.
Aの因子を整えています.Aの正の整数を全部取り除きます.12のような因子は、1、2、3、4、5、6です.
問題の分析:
単なる遍歴にすぎません.1000以内の条件を満たすすべての親密数を検索します.本題は求める数の因子と、その複雑さを減らすための関数を使用します.
#include <stdio.h>
int fsum(int a)
{
int i, sum = 1;
for (i=2; i<=a/2; i++)
if(a%i==0)
sum += i;
return sum;
}
int main()
{
int a, b, c;
for (a=1; a<=10000; a++)
{
b = fsum(a);
c = fsum(b);
if ( a==c && b!=a)
printf("%8d,%8d
", a, b);
}
return 0;
}
/**********************************
：
220, 284
284, 220
1184, 1210
1210, 1184
2620, 2924
2924, 2620
5020, 5564
5564, 5020
6232, 6368
6368, 6232
**********************************/3.正方形の定理
問題の説明:
プログラミング検証「正方定理」:いずれの自然数も四つの数の平方和によって表現できます.
問題の分析:
このような問題の最も主要なのは循環変数の開始と終了を考慮して値を取ることです.このプログラムには4サイクルが使われています.実は3サイクルだけでこの問題を解決できます.試してみてください.
#include "math.h"
#include "stdlib.h"
void check_(int i)
{
int arr_[4]; // 4
int t;
t = i;
for (arr_[0]=sqrt(t); arr_[0]>=sqrt(t/2); arr_[0]--)
{
t -= arr_[0] * arr_[0];
for (arr_[1]=sqrt(t); arr_[1]>=sqrt(t)/2; arr_[1]--)
{
t -= arr_[1] * arr_[1];
for (arr_[2]=sqrt(t); arr_[2]>=sqrt(t)/2; arr_[2]++)
{
t -= arr_[2] * arr_[2];
for (arr_[3]=sqrt(t); arr_[3]>=sqrt(t)/2; arr_[3]++)
if (arr_[0]*arr_[0]+arr_[1]*arr_[1]+arr_[2]*arr_[2]+arr_[3]*arr_[3]==i)
{
printf("%5d %5d %5d %5d",arr_[0],arr_[1],arr_[2],arr_[3]);
exit(0);
}
}
}
}
printf(" !");
}
int main()
{
int n;
printf(" :");
scanf("%d",&n);
check_(n);
return 0;
}
/**********************************
：
:12
3 1 1 1
**********************************/4、百元問題
問題の説明:
王おばさんは100元で100頭の小さい家畜を買います.多くは「百元」を要求していません.子牛は頭10元で、子羊は一匹3元で、うさぎは0.5元です.彼女の代わりにどうやって買うべきですか?
問題の分析:
変数i,jでそれぞれ牛、羊の頭の数を表します.牛を買うにはI*10元、羊を買うにはi*3元が必要です.この時、残りのお金と残りのお金を計算してウサギの頭の数を買うことができます.3種類の小家畜の総頭数によって解を求めることができます.
#include "stdlib.h"
int main()
{
int i, j, k, m;
for (i=0; i<=10; i++)
for (j=0; j<=(100-i*10)/3; j++)
if ((i+j+(100-i*10-j*3)*2) == 100)
printf("%d %d %d
",i,j,(100-i*10-j*3)*2);
return 0;
}
/**********************************
：
0 20 80
5 1 94
**********************************/5.連続と数
問題の説明:
十三個の連続の自然数を探してください.全部合数です.
問題の分析:
「合数」とは、素数ではなく、次の解法は合数の印としてflagsを使い、カウントします.
#include "stdlib.h"
#include <math.h>
int main()
{
int count = 0, i = 9, j , flag;
do
{
flag = 0;
for (j=3; j<=sqrt(i); j++)
if (i%j==0)
flag=1;
if (flag==0)
count = 1;
else
count += 2;
i += 2;
}while (count<13);
for (j=i-13; j<i;j++)
printf("%d ",j);
return 0;
}
/**********************************
：
114 115 116 117 118 119 120 121 122 123 124 125 126
**********************************/6*貧乏なやり方で0—1リュックサックの問題を解決します.
問題の説明:
選択したものの総重量は指定の制限重量を超えないようにします.ただし、選択したものの価値は最大です.
問題の分析:
n個の物品の重さと価値をそれぞれ保存に設定して配列w[]とv[]の中で、制限重量はtwです.一つのn元グループ(x 0,x 1,…,xn-1)を考慮します.このうち、xi=0はi番目のものが選択されていないことを示していますが、xi=1はi番目のものが選択されていることを示しています.エニュメレーションでリュックサックの問題を解決するには、すべての選択肢を列挙する必要があります.
各成分の取得値は0または1のn元グループの個数は2 n個であることは明らかであるが、各n元グループは実際には1つの長さnの2進数に対応しており、これらの2進数の取得範囲は0〜2 n−1である.したがって、0〜2 n−1をそれぞれ対応する2進数に変換すれば、必要な2 n個のn元グループを得ることができる.
#include <stdio.h>
#include <math.h>
#define MAX 100 //
/* n ， b */
void conversion(int n,int b[MAX])
{
int i;
for(i=0;i<MAX;i++)
{
b[i] = n%2;
n = n/2;
if(n==0)break;
}
}
int main()
{
int i,j,n,b[MAX],temp[MAX];
float tw,maxv,w[MAX],v[MAX],temp_w,temp_v;
printf("please input n:
");
scanf("%d",&n); //
printf("please input tw:");
scanf("%f",&tw); //
/* */
for(i=0;i<n;i++)
{
printf("please input the weight of w[%d]:
",i);
scanf("%f",&w[i]);
}
/* */
for(i=0;i<n;i++)
{
printf("please input the value of v[%d]:
",i);
scanf("%f",&v[i]);
}
maxv = 0;
/* 2n ， */
for (i=0;i<pow(2,n);i++)
{
for (j=0;j<n;j++)
{
b[j] = 0;
}
conversion(i,b);
temp_v = 0;
temp_w = 0;
for (j=0;j<n;j++)
{
if (b[j]==1)
{
temp_w = temp_w+w[j];
temp_v = temp_v + v[j];
}
}
/* ， */
if ((temp_w < tw)&&(temp_v>maxv))
{
for (j=0;j<n;j++)
{
temp[j] = 0;
}
maxv = temp_v;
for (j=0;j<n;j++)
{
temp[j] = b[j];
}
}
}
printf("the max values is %f:
",maxv); //
printf("the selection is:
");
/* */
for (j=0;j<n;j++)
{
printf("%d ",temp[j]);
}
return 0;
}
/**********************************
：
please input n:
3
please input tw:100
please input the weight of w[0]:
30
please input the weight of w[1]:
80
please input the weight of w[2]:
60
please input the value of v[0]:
20
please input the value of v[1]:
70
please input the value of v[2]:
60
the max values is 80.000000:
the selection is:
1 0 1
**********************************/