練習題(一)

2016-01-23

680
0
練習題
2016-01-26

假設P是某個整數Q的完全平方數( P=Q^2)。
寫一個函式:

int solution(int A, int B)

給定兩個整數A和B，然後B>=A，然後回傳在A和B區間內所有的完全平方數個數(包含A和B)。

例如: A=3 B=26，然後我們應該要回傳4，因為在3到26中間有4個完全平方數。
4=2^2, 9=3^2, 16=4^2, 25=5^2.

本文以C#實作執行。

完整程式碼如下:

using System;

namespace 練習題一
{
    class Program
    {

        public static double sqrt(int x)
        {
            double small = 0.000000001;
            double low, high;

            if (x < 0) return -1;

            if (x < 1)
            {
                low = 1; high = x;
            }
            else
            {
                low = 1;
                high = x;
            }

            while (high - low > small)
            {
                double mid = (low + high) / 2;
                if (mid * mid > x)
                {
                    high = mid;
                }
                else
                {
                    low = mid;
                }
            }

            return low;
        }

        public static int solution(int A, int B)
        {
            if ((int)(sqrt(A + 1)) > (int)(sqrt(A)) && (int)(sqrt(B + 1)) <= (int)(sqrt(B))) //處理下限為平方數 上限不為平方數
                return (int)sqrt(B) - (int)(sqrt(A - 1));
            else if ((int)(sqrt(B + 1)) > (int)(sqrt(B)) && (int)(sqrt(A + 1)) <= (int)(sqrt(A))) //處理上限為平方數 下限不為平方數
                return (int)sqrt(B - 1) - (int)(sqrt(A)) + 1;
            else if ((int)(sqrt(A + 1)) > (int)(sqrt(A)) && (int)(sqrt(B + 1)) > (int)(sqrt(B))) //處理上限下限皆為平方數
                return (int)sqrt(B - 1) - (int)(sqrt(A-1)) + 1;
            else //處理 上限下限皆不為平方數
                return (int)sqrt(B) - (int)(sqrt(A));
        }

        static void Main(string[] args)
        {

            Console.Write("請輸入區間的下限:");
            int small = int.Parse(Console.ReadLine());
            Console.Write("請輸入區間的上限:");
            int large = int.Parse(Console.ReadLine());

            Console.Write("["+small+".."+large+"]"+"="+ solution(small, large));

            Console.ReadKey();
        }
    }
}

執行結果如下:

下限為平方數,上限不為平方數
4,9,16,25,36,49,64,81

下限不為平方數,上限為平方數
9,16,25,36,49,64,81,100

上限下限皆為平方數
4,9,16,25,36,49,64,81,100

上限下限皆不為平方數
4,9,16,25,36,49,64,81,100

有夢最美築夢踏實

活在當下認真過每一天

我是阿夢也是Ace

回首頁