ゼロ学習アルゴリズムコンテスト3:aabb問題から


タイトルの説明:
aabbのようなすべての形の4ビットの完全な平方数(すなわち、前の2桁の数字は等しく、後の2桁の数字も等しい)を出力します.
分岐とループが結合すると機能が強くなります.以下に可能なすべての結果aabbを列挙し、それらが完全な平方数であるかどうかを判断します.注意aの範囲は1~9であるが、bは0であってもよく、メインプログラムは以下の通りである.
                                     for(int a=1;a<=9;a++)
                                          for(int b=0;b<=9;b++)
If(aabbは完全二乗)
                                                           printf(“%d”,aabb);
上のプログラムは完全ではありません——“aabbは完全な平方数です”は中国語の説明で、合法的なC言語の表現式ではありませんて、aabbはC言語の中でもう一つの変数で、2つの数字aとbをつなぎ合わせるのではありません.このような「本物のプログラムではない」「コード」を偽コード(pseudocode)とする.正規の偽コードの定義はいくつかあるが、実際の応用では、コードのフォーマットにあまりこだわる必要はない.主な目標はアルゴリズムの概要を記述し、細部を避け、構想を啓発することである.
擬似コードを用いてアルゴリズムを考え記述することは推奨すべき方法である.
偽のコードを書いた後、それを本当のコードにする方法を考える必要があります.上の偽コードには2つの「不法」な場所があります.完全二乗数判定とaabbという変数.後者は比較的容易である.別の変数n=aで×1100+b×11を保存すればよい.
疑似コードをコードに書く場合は、簡単なタスクを選択して完了するのが一般的です.
次の問題は少し困難になります:どのようにnが完全な平方数であるかどうかを判断しますか?
方法1:
#include
#include
int main()
{
   for(int a=1;a<=9;a++)
      for(int b=0;b<=9;b++)
      {
	 int n=a*1100+b*11;//      n,       n
	 int m=floor(sqrt(n)+0.5);
   	 if(m*m==n)
	    printf("%d
",n); } return 0; }

このように書いてもいいですか.If(sqrt(n)==floor(sqrt(n))) printf(“%d”,n);すなわち、sqrt(n)が整数であるか否かを直接判断する.理論的にはもちろん問題ありませんが、浮動小数点数の演算(と関数)に誤差がある可能性があるため、このように書くのは保険ではありません.大量の計算後、誤差の影響で整数1が0.999999999になり、floorの結果は1ではなく0になると仮定します.誤差の影響を低減するために、一般的には四捨五入、すなわちfloor(x+0.5)に変更する.理解が困難であれば、1単位区間を数軸上で0.5単位左にシフトする距離を想像することができる.Floor(x)が1に等しい区間は【1,2】であり、floor(x+0.5)が1に等しい区間は【0.5,1.5】である.
浮動小数点演算に誤差がある可能性があります.さらに浮動小数点演算比較を行う場合は,浮動小数点誤差を考慮すべきである.
まとめ:小数部が0.5の数も浮動小数点誤差の影響を受けるため,どの厳密なアルゴリズムコンテストの問題もこの問題を解決する方法を考えなければならない.
もう1つの考え方は、平方根xを列挙し、開方操作を回避することである.
      
#include
int main()
{
   for(int x=33;;x++)     //for          
   {
      int n=x*x;
      if(n>9999)
         break;
      int high=n/100;
      int low=n%100;
      if(high/10==high%10&&low/10==low%10)
	 printf("%d
",n); } return 0; }

答えは7744です.