0

ここに、1 から 20 までのすべての数値で最小の倍数を見つける C# で書かれたコードがあります。ただし、正しい答えが得られるまでに実行に時間がかかったので、非常に非効率的です。コードを改善するためにできるさまざまな方法を知りたいです。ありがとうございました。

        public static void SmallestMultiple()
    {
        const ushort ARRAY_SIZE = 21;
        ushort[] array = new ushort[ARRAY_SIZE];
        ushort check = 0;
        for (uint value = 1; value < uint.MaxValue; value++)
        {
            for (ushort j = 1; j < ARRAY_SIZE; j++)
            {
                array[j] = j;
                if (value % array[j] == 0)
                {   
                    check++;
                }
            }
            if (check == 20)
            {
                Console.WriteLine("The value is {0}", value);
            }
            else
            {
                check = 0;
            }
        }
    }
4

6 に答える 6

2 
    static void Main(string[] args)
    {
        int[] nums = Enumerable.Range(1, 20).ToArray();
        int lcm = 1;

        for (int i = 0; i < nums.Length; i++)
        {
            lcm = LCM(lcm, nums[i]);
        }
        Console.WriteLine("LCM = {0}", lcm);
    }

    public static int LCM(int value1, int value2)
    {
        int a = Math.Abs(value1);
        int b = Math.Abs(value2);

        // perform division first to avoid potential overflow
        a = checked((a / GCD(a, b)));
        return checked((a * b));
    }

    public static int GCD(int value1, int value2)
    {
        int gcd = 1;     // Greates Common Divisor

        // throw exception if any value=0
        if (value1 == 0 || value2 == 0)
        {
            throw new ArgumentOutOfRangeException();
        }

        // assign absolute values to local vars
        int a = Math.Abs(value1);            // local var1
        int b = Math.Abs(value2);            // local var2

        // if numbers are equal return the first
        if (a == b) { return a; }
            // if var "b" is GCD return "b"
        if (a > b && a % b == 0) { return b; }
            // if var "a" is GCD return "a"
        if (b > a && b % a == 0) { return a; }

        // Euclid algorithm to find GCD (a,b):
        // estimated maximum iterations: 
        // 5* (number of dec digits in smallest number)
        while (b != 0)
        {
            gcd = b;
            b = a % b;
            a = gcd;
        }
        return gcd;
    }
}

ソース:高速整数アルゴリズム: 最大公約数と最小公倍数、.NET ソリューション

于 2013-01-30T08:36:32.770 に答える
2

また、結果は 19 (最大の素数) で 20 まで割り切れる必要があるため、19 の倍数だけを循環させることができます。

これにより、約 19 倍速く結果が得られるはずです。

これを行うコードは次のとおりです。

public static void SmallestMultiple()
{
    const ushort ARRAY_SIZE = 21;
    ushort[] array = new ushort[ARRAY_SIZE];
    ushort check = 0;

    for (uint value = 19; value < uint.MaxValue; value += 19)
    {
        for (ushort j = 1; j < ARRAY_SIZE; j++)
        {
            array[j] = j;
            if (value % array[j] == 0)
            {
                check++;
            }
        }
        if (check == 20)
        {
            Console.WriteLine("The value is {0}", value);
            return;
        }
        else
        {
            check = 0;
        }
    }
}

232792560私のマシンでは、これは2 秒強で結果を見つけます。

アップデート

また、最初のプログラムは解に到達しても停止しなかったことに注意してください。return止めるようにとの文言を追加しました。

于 2013-01-30T08:29:36.423 に答える
2

1 から 20 までの数字の最小公倍数を探しているだけです。

方式

ユークリッド アルゴリズムを使用して GCD を効率的に計算できる場合。

私は C# を知りませんが、この Python ソリューションを翻訳するのは難しくありません。

def gcd(a, b):
    while b != 0:
       a, b = b, a % b

    return a

def lcm(a, b):
    return (a * b) / gcd(a, b)

numbers = range(1, 20 + 1)

print reduce(numbers, lcm)

それもかなり速いです：

>>> %timeit reduce(lcm, range(1, 20000))
1 loops, best of 3: 258 ms per loop
于 2013-01-30T08:34:11.917 に答える
1

編集: v2.0 - 大幅な速度向上

w0lfのソリューションに基づいています。より高速なソリューション:

public static void SmallestMultiple()
{
    // this is a bit quick and dirty
    //   (not too difficult to change to generate primeProduct dynamically for any range)
    int primeProduct = 2*3*5*7*11*13*17*19;
    for (int value = primeProduct; ; value += primeProduct)
    {
       bool success = true;
        for (int j = 11; j < 21; j++)
        {
            if (value % j != 0)
            {
                success = false;
                break;
            }
        }
        if (success)
        {
            Console.WriteLine("The value is {0}", value);
            break;
        }
    }
}

x で割り切れる場合 (例: 12)、x/n で割り切れる場合 (例: 12/2 = 6) であるため、1-10 をチェックする必要はありません。最小の倍数は常に、関連するすべての素数の積の倍数になります。

C# ソリューションのベンチマークは行いませんでしたが、同等の Java ソリューションは約 0.0000006 秒で実行されます。

于 2013-01-30T09:04:08.343 に答える
0

ここで何を達成しようとしているのか正確にはわかりませんが、外側の for ループは約 4,294,967,295 時間 (uint.MaxValue) 実行されます。そのため、少し時間がかかります...

uint.MaxValue に行かないようにする方法がある場合 - 必要なことを達成したときにループを壊すなど - それはそれをスピードアップします。

また、array[j] を j に設定しているため、明らかに配列を再び使用することはありません。

value % j

それ以外の

value % array[j]
于 2013-01-30T08:30:15.010 に答える
0

W0lfによって書かれたコードも使用します（申し訳ありませんが、あなたの投稿にコメントすることはできません）私は役に立たないと思う配列を削除して（少しだけ）改善します..

public static void SmallestMultiple()
{
    const ushort ARRAY_SIZE = 21;
    ushort check = 0;
    for (uint value = 1; value < uint.MaxValue; value++)
    {
        for (ushort j = 1; j < ARRAY_SIZE; j++)
        {
            if (value % j == 0)
            {   
                check++;
            }
        }
        if (check == 20)
        {
            Console.WriteLine("The value is {0}", value);
        }
        else
        {
            check = 0;
        }
    }
}
于 2013-01-30T08:34:09.720 に答える