Chris Maunder Ответов: 12

Вызов кода: наибольший общий знаменатель

Наибольший Общий Знаменатель


Сегодняшний вызов, посланный Бобом Хентом, - это старый и хороший.

Дан список целых чисел вида: (n0, n1, n2, ... nx)
Где (0 < n ≤ 10000) и (x < 500)
Возвращает наибольший общий делитель (GCD), где GCD определяется как наибольшее положительное целое число, которое делит все числа без остатка.

Пример:

Дано: [247, 8645, 1216, 3648]
Возвращение: 19
Потому что: 247/19 = 13, 8645/19 = 455, 1216/19 = 64, 3648/19 = 192

Приз - кружка CodeProject. Очки за самый неожиданный код. Вырезание и склеивание из interwebz даст вам решение, но никаких очков. Немного напрягите свой ум.

Что я уже пробовал:

Оставаться в здравом уме.

Победитель прошлой недели-из Фрейзер Дути[^], хотя особые упоминания относятся к ProgramFox (для самых противных) и H2O-au (для самых аккуратных).

Присылайте свои идеи на следующую неделю и не забудьте проголосовать за опубликованные работы!

PIEBALDconsult

"Очки за самый неожиданный код"

Возможно, мне придется создать язык под названием "Испанская инквизиция".

Graeme_Grant

-не забудьте проголосовать за те записи, которые будут опубликованы!"

PIEBALDconsult

Гомик не играет в дат.

Jon McKee

Мне нравится, что нет голосов ни за одно решение =D каждый считает свое решение лучшим (я не исключение).

Graeme_Grant

Либо это, либо никто другой, кроме людей, подающих решения, не смотрит на них...

Jon McKee

Очень верный. Вероятно, было бы лучше, если бы вызов был перекрестно вывешен в гостиной, как и первый.

PIEBALDconsult

Я стараюсь не голосовать ни за себя, ни против.

12 Ответов

Рейтинг:
64

Kornfeld Eliyahu Peter

Наконец я добрался до завершения сборки 6502... Я использовал эмулятор C64 в качестве хоста для кода,так что помимо фактического вычисления есть еще несколько строк для вывода результата...

Самое интересное, что 6502-это не только 8-битный процессор (так что не 16-битная арифметика), но и не имеет встроенного умножения или деления. Поэтому мне пришлось обрабатывать 16-битное вычитание и создавать 16-битное умножение... Кроме того, это реализация бинарного решения...

Прежде всего, вот скриншот C64 после запуска кода: НОД-С64.формат PNG (15.7 КБ)

Для тех, кто хочет его запустить, нужно загрузить PRG-файл: gcd.zip (.6 КБ) (застегивается на молнию, чтобы я мог загрузить его)

Здесь ассемблерный код написан на C64Studio:

; GREATEST COMMON DENOMINATOR

; HELPERS

; KERNEL CALLS
CHROUT = $FFD2 ; PRINT A CHAR

; BASIC CALLS
N2A = $BDCD ; PRINT A NUMBER
STROUT = $AB1E ; PRINT ZERO TERMINATED STRING

; MACRO
!MACRO PRINT_MSG ADDR {
  PHA
  TXA
  PHA
  TYA
  PHA
  
  LDA #<ADDR
  LDY #>ADDR
  JSR STROUT

  PLA
  TAY
  PLA
  TAX
  PLA
}

* = $0801 ; BASIC LOADER
!BYTE $0C,$08,$0A,$00,$9E,$20,$38,$31,$39,$32,$00,$00,$00 ; 10 SYS 8192

*=$2000 ; CODE SEGMENT  
  LDA COUNT
  ASL
  STA LENGTH

  +PRINT_MSG TITLE_MSG
  
  JSR PRINT_DATA
MAIN_LOOP
  LDX COUNT
  STX INDEX
  DEC INDEX
  
  LDX #$00

INNER_LOOP  
  ; CHECK FIRST NUMBER FOR ZERO
  LDY VALUES,X
  CPY #$00
  BNE CHECK2
  LDA VALUES+1,X
  CMP #$00
  BEQ ZERO

  ; CHECK SECOND NUMBER FOR ZERO
CHECK2
  LDY VALUES+2,X
  CPY #$00
  BNE NO_ZERO
  LDA VALUES+3,X
  CMP #$00
  BEQ ZERO
  
  ; BOTH NUMBERS ARE NON-ZERO
NO_ZERO
  LDA VALUES,X
  STA VALUE1
  LDA VALUES+1,X
  STA VALUE1+1

  LDA VALUES+2,X
  STA VALUE2
  LDA VALUES+3,X
  STA VALUE2+1

  JSR GCD2
  
  LDA VALUE1
  STA VALUES,X
  LDA VALUE1+1
  STA VALUES+1,X

  INX
  INX
  
  DEC INDEX
  BNE INNER_LOOP  
  
  DEC COUNT
  LDA COUNT
  CMP #$01
  BNE MAIN_LOOP
  
  +PRINT_MSG ANSWER_MSG

  LDX VALUES
  LDA VALUES+1
  JSR N2A
  
  JMP END
  
ZERO
  +PRINT_MSG NO_ZERO_MSG

END  
  RTS

PRINT_DATA
  PHA
  TXA
  PHA
  TYA
  PHA

  +PRINT_MSG LIST_MSG

  LDY #$00
  
LOOP
  STY INDEX
  LDX VALUES,Y
  LDA VALUES+1,Y
  JSR N2A
  LDA #$2C
  JSR CHROUT
  LDY INDEX
  INY
  INY
  CPY LENGTH
  BNE LOOP

  LDA #$14
  JSR CHROUT
  LDA #$0D
  JSR CHROUT
    
  PLA
  TAY
  PLA
  TAX
  PLA
  
  RTS
  
GCD2
  PHA
  TXA
  PHA
  TYA
  PHA
  
  LDA #$00
  STA POWER

GCD_LOOP
  LDA VALUE1
  CMP VALUE2
  BNE DIFFERENT
  LDA VALUE1+1
  CMP VALUE2+1
  BNE DIFFERENT

  JMP FOUND
  
DIFFERENT
  CLC
  LDA VALUE1
  LSR
  BCS VALUE_ODD
  CLC
  LDA VALUE2
  LSR
  BCS VALUE_ODD
  
  CLC
  LSR VALUE1+1
  ROR VALUE1
  
  CLC
  LSR VALUE2+1
  ROR VALUE2
  
  INC POWER
  JMP GCD_LOOP
  
VALUE_ODD
  CLC
  LDA VALUE1
  LSR
  BCS VALUE1_ODD
  
  CLC
  LSR VALUE1+1
  ROR VALUE1

  JMP GCD_LOOP

VALUE1_ODD
  CLC
  LDA VALUE2
  LSR
  BCS ALL_ODD
  
  CLC
  LSR VALUE2+1
  ROR VALUE2

  JMP GCD_LOOP
  
ALL_ODD
  LDA VALUE1+1
  CMP VALUE2+1
  BCC V1_LT_V2
  BNE V1_GT_V2
  LDA VALUE1
  CMP VALUE2
  BCC V1_LT_V2

V1_GT_V2
  SEC       
  LDA VALUE1
  SBC VALUE2
  STA VALUE1
  LDA VALUE1+1
  SBC VALUE2+1
  STA VALUE1+1
  
  CLC
  LSR VALUE1+1
  ROR VALUE1

  JMP GCD_LOOP

V1_LT_V2
  SEC       
  LDA VALUE2
  SBC VALUE1
  STA VALUE2
  LDA VALUE2+1
  SBC VALUE1+1
  STA VALUE2+1
  
  CLC
  LSR VALUE2+1
  ROR VALUE2

  JMP GCD_LOOP

FOUND
  LDA #$01
COMPUTE_POWER
  LDX POWER
  BEQ COMPUTE_FINAL
  ASL
  DEC POWER
  JMP COMPUTE_POWER
  
COMPUTE_FINAL
  STA POWER
  LDA #$00
  STA TEMP
  STA TEMP+1
  
COMPUTE_LOOP
  CLC
  LDA VALUE1
  ADC TEMP
  STA TEMP
  LDA VALUE1+1
  ADC TEMP+1
  STA TEMP+1
  DEC POWER
  BNE COMPUTE_LOOP
  
  LDA TEMP
  STA VALUE1
  LDA TEMP+1
  STA VALUE1+1
  
  PLA
  TAY
  PLA
  TAX
  PLA
  
  RTS
  
*=$2400 ; DATA SEGMENT
VALUES
  !WORD 247, 8645, 1216, 3648
VALUE1
  !WORD 0
VALUE2
  !WORD 0
TEMP
  !WORD 0
COUNT
  !BYTE 4
INDEX
  !BYTE 0
LENGTH
  !WORD 0
POWER
  !BYTE 0
TITLE_MSG
  !TEXT $81, $93, "       CODEPROJECT CODE CHALLENGE", 13, "        GREATEST COMMON DIVISOR!", $9A, 13, 13, 0
NO_ZERO_MSG
  !TEXT $96, "NAN", $9A, 13, 0
LIST_MSG
  !TEXT $81, "NUMBERS:", $9A, 13, "  ", 0
ANSWER_MSG
  !TEXT $81, "GCD:", $9A, 13, "  ", 0

Рейтинг:
2

CPallini

Это и есть алгоритм решения 2, улучшенные с помощью ПЕГИЙпредложения, и портирована на C# для упрощения сравнения с другими алгоритмами.
По моему скромному мнению (:- D ) это удивительно быстро.

static uint gcd(uint[] a)
{ 
  uint iom = 0;
  uint min;
  uint i;
  uint len = (uint)a.Length;

  // find index of minimum (iom)  
  for (i = 1; i < len; ++i)
    if (a[iom] > a[i]) iom = i; 
  
  // move minimum to a[0]
  min = a[iom];
  a[iom] = a[0];
  a[0] = min;
	
  while ( len > 1)
  {
    if (a[0] == 1) return 1;
    len = reminders(a, len);
  }
   return a[0];
}

static uint reminders(uint [] a, uint len)
{
  // find the reminders, at the same time find new minimum and remove zeroes
  uint iom = 0;
  uint i=1;
  while (i<len)
  {
    a[i] %= a[0];
    if (a[i] == 0)
    {
      a[i] = a[len-1];
      --len;
    }
    else
    {
      if (a[i] < a[iom])
        iom = i;
      ++i;
    }
  }
  if (iom>0)
  { // move min to a[0]
    uint tmp = a[0];
    a[0] = a[iom];
    a[iom] = tmp;
  }
  return len;
}

Рейтинг:
2

Kornfeld Eliyahu Peter

Там не так много осталось, как вся используемая математика, но я на пути к созданию решения 6502 (на C=64), поэтому я создал прототип JavaScript, чтобы показать, что это можно сделать, фактически ничего не разделяя...

var a = [266, 8664, 1216, 3648];
var l = a.length;

while (l > 1)
{
    for (var k = 0; k < l - 1; k++)
    {
        if ((a[k] == 0) || (a[k + 1] == 0))
        {
            a[0] = NaN;
            break;
        }

        a[k] = gcd(Math.abs(a[k]), Math.abs(a[k + 1]));
    }

    if (isNaN(a[0])) break;

    l--;
}

// a[0] is the GCD

function gcd(x, y) {
    var d = 0;

    do
    {
        if (x == y) return x * Math.pow(2, d);

        if (!(x & 1) && !(y & 1))
        {
            x = x >> 1;
            y = y >> 1;

            d++;

            continue;
        }

        if (!(x & 1))
        {
            x = x >> 1;

            continue;
        }

        if (!(y & 1))
        {
            y = y >> 1;

            continue;
        }

        if (x > y) x = (x - y) >> 1;
        if (y > x) y = (y - x) >> 1;
    } while (true);
}

Live - JSFiddle[^]

Graeme_Grant

Если вы посмотрите на другие решения выше, они тоже не используют деление. Также известный как двоичный GCD.

Kornfeld Eliyahu Peter

Кроме вашего решения все используют % или даже /...
Однако моя точка зрения была направлена на 6502 - там нет деления или умножения, только сложение и вычитание...

Рейтинг:
2

H2O-au

Кэширование простых факторов

Что мне кажется интересным в этой проблеме, так это низкое значение nмаксимум = 10,000.
* Существует только 1229 простых чисел меньше 10 000 (Самое большое из которых-9 973)
* Все целые числа меньше 10 000 имеют не более 13 простых множителей (начиная с 214 = 16 384 > 10 000)

Ну и что с того, что мы потратили некоторое время на то, чтобы кэшировать простые множители каждого возможного входного целого числа?

Математика: каждое число (n) является произведением всех простых чисел меньше самого себя (pя), каждый из которых возведен в некоторую степень (ая). GCD - это набор минимальных мощностей по всем тестовым номерам

Наибольшее возможное число простых множителей (наибольшее значение aя) будет 13 - так что мы можем кэшировать эти полномочия в виде байтов. Полный массив 2D размером 10 000 x 1229 байт составляет 95,1 МБ, что, вероятно, не является необоснованным.

Но этот 2D-массив состоит в основном из нулей (по крайней мере, 1216 степеней из 1229 равны нулю), поэтому использование массива пар ключ-значение сокращает его до ~1,2 мб. Сжатие массива таким образом также будет иметь преимущества в скорости.

Наш кэш будет содержать множество простых чисел меньше nмаксимум, и массив словарей, по одному для каждого целого числа меньше nмаксимум, который связывает каждое простое число (индексируемое ushort) с силой (хранящейся в виде byte).

Теперь код... (Извини, что не самый аккуратный, но пока сойдет.)

using PrimeFactorCollection = Dictionary<ushort, byte>;

public class CachedGcdFetcher
{
    const int MaxAllowableMaxAllowableValue = 821640;
    const double ATinyBitMoreToBeOnTheSafeSide = 1e-6;

    public int MaxAllowableValue { get; private set; }

    int[] primes;
    PrimeFactorCollection[] primeFactorCache;

    ...

}

Обратите внимание, что MaxAllowableValue (северныймаксимум = 10 000) имеет верхний предел. Поскольку мы используем ushort при индексации простых чисел для экономии оперативной памяти мы можем обрабатывать только 65 535 простых чисел. Так что Нмаксимум &ЛТ; 65,536 тыс. премьера (821,641).

Сам кэш - это два поля int[] primes и PrimeFactorCollection[] primeFactorCache.

Далее, некоторые вспомогательные функции.

static bool isPrime(int x)
{
    var maxPossibleFactor = (int)Math.Floor(Math.Sqrt(x)
        + ATinyBitMoreToBeOnTheSafeSide);

    return !Enumerable.Range(2, maxPossibleFactor)
        .Any(a => x % a == 0);
}

int pfCollectionToNumber(PrimeFactorCollection c)
{
    var output = 1;
    foreach (var f in c)
    {
        var p_i = primes[f.Key];
        for (int a_i = 0; a_i < f.Value; a_i++)
        {
            output *= p_i;
            if (output > MaxAllowableValue)
                return output;
        }
    }
    Console.WriteLine(output);
    return output;
}

PrimeFactorCollection indicesToPfCollection(IEnumerable<ushort> pfIndices)
{
    var a = new PrimeFactorCollection();
    foreach (var ig in pfIndices.GroupBy(i => i))
        a.Add(ig.Key, (byte)ig.Count());
    return a;
}

Кэш строится в конструкторе, и GCD извлекается в него int GetGcd(int[] ints).

public CachedGcdFetcher(int maxAllowableValue)
{
    // Valiate parameter
    if (maxAllowableValue < 2 || MaxAllowableValue >= MaxAllowableMaxAllowableValue)
        throw new ArgumentOutOfRangeException(
            nameof(maxAllowableValue),
            maxAllowableValue,
            "This class can only handle numbers in the range [2, " 
                + MaxAllowableMaxAllowableValue + "].");

    // Initialise properties
    this.MaxAllowableValue = maxAllowableValue;
            
    // Build a cache of primes
    primes = Enumerable.Range(2, MaxAllowableValue)
        .Where(isPrime)
        .ToArray();
            
    // Build a cache of prime factors by checking prime divisibilities
    primeFactorCache = new PrimeFactorCollection[MaxAllowableValue + 1];
    for (int n = 2; n < primeFactorCache.Length; n++)
    {
        // Keep a list of prime factors with non-zero powers
        var pfs = new List<KeyValuePair<ushort, byte>>();

        for (ushort i = 0; i < primes.Length; i++)
        {
            var nr = n;
            var p_i = primes[i];
            byte a = 0;
            while (nr % p_i == 0)
            {
                a++;
                nr /= p_i;
            }
            if (a > 0)
                pfs.Add(new KeyValuePair<ushort, byte>(i, a));
        }

        // Transfer the prime factors to a dictionary (with known capacity)
        var pfs2 = new PrimeFactorCollection(pfs.Count);
        foreach (var pf in pfs)
            pfs2.Add(pf.Key, pf.Value);

        primeFactorCache[n] = pfs2;
    }
}

public int GetGcd(int[] ints)
{
    // We are reliant on good data, so validate
    foreach (var n in ints)
        if (n < 2 || n > MaxAllowableValue)
            throw new ArgumentOutOfRangeException(
                nameof(ints),
                "All values of input array should be in range [2, "
                    + n + "]");

    // Lookup cache for each input n, and collect all prime factors
    var indices = new List<ushort>();
    foreach (var n in ints)
        foreach (var f in primeFactorCache[n])
            if (!indices.Contains(f.Key))
                indices.Add(f.Key);

    // Set up output prime factor collection
    var outputFactors = new PrimeFactorCollection();
    foreach (var i in indices)
        outputFactors.Add(i, byte.MaxValue);

    // Find minimum powers
    foreach (var i in indices)
    foreach (var n in ints)
    {
        var c = primeFactorCache[n];
        if (!c.ContainsKey(i))
            // if not in collection, it's a zero
            outputFactors[i] = 0;
        else
            // if in collection, take the smallest
            outputFactors[i] = Math.Min(outputFactors[i], c[i]);
    }

    // Build GCD
    return pfCollectionToNumber(outputFactors);
}

Стандартный отказ от ответственности: это не полностью проверено за пределами примера (он сказал 19! Ура!). Я быстро проверил использование памяти (~1,2 мб) и скорость (кэш строится за ~170 МС). Я понятия не имею, действительно ли это дает преимущество в производительности по сравнению с другими методами. Я мог бы сделать некоторые тесты производительности против других алгоритмов позже...

PIEBALDconsult

Разве вам не нужны простые числа только до квадратного корня из Nmax (или половины)?

Jon McKee

Определенно, у меня есть преимущество по использованию памяти (21 МБ), но у меня есть вы по скорости. Я не опубликовал его, потому что в этом нет никакого смысла, но я изменил свой алгоритм, чтобы использовать uint для удвоения диапазона чисел. Я могу запустить 1 000 000 чисел в диапазоне 0 <= n <= 4 285 200 000 за ~155 МС =)

PIEBALDconsult

Что касается кэширования, то почему бы не добавлять числа и их простые множители только по мере их появления во входных данных?

Рейтинг:
1

Maciej Los

Что ж... Многие из вас знают, что я фанат решений Linq!

//given list
int[] givenlist = new int[]{247, 8645, 1216, 3648};
//int[] givenlist = new int[]{5, 12, 316, 648}; //gcd: 1

//get the list of divisors from 1 to min of given list
//gcd cannot be greater then min of given list
int[] divisors = Enumerable.Range(1, givenlist.Min()).ToArray();
//all numbers from given list divide by all dividors

//cross join: numbers and divisors
//get only those numbers with 0 as remainder
//group data by divisor
//get a list of common divisors (at least there must be only 1)
//get GCD
var gcd = divisors
	.SelectMany(gl=> givenlist, (di, gl) => new {divisor=di, number=gl})
	.Where(a=>a.number % a.divisor==0)
	.GroupBy(x=> x.divisor)
	.Where(grp=>grp.Count()==givenlist.Length)
	.Max(a=>a.Key);


Примечание: приведенный выше код выполняется менее чем за 0,001 секунды.

Я надеюсь, что мой нетрадиционный способ найти GCD вызовет у вас интерес.

Chris Maunder

Это так ужасно, это потрясающе! +1

Maciej Los

- Спасибо, Крис.

Рейтинг:
1

CPallini

Алго работает примерно так

  • найдите минимум списка.
  • замените каждый пункт списка (но минимальный) напоминанием о себе, разделенным на минимум.
  • удалите все нули (сокращая список).

Описанные шаги повторяются до тех пор, пока:
  • в списке есть только один пункт: успех, пункт является решением

или
  • минимум-1: успех, 1-это решение


[исправлено после Джон Макки замечание]

Код дает более точное определение:
int index_of_min( int a[], int len)
{
  int index = 0;
  int i;
  for ( i=0; i<len; ++i)
  {
    if (a[index] > a[i])
      index = i;
  }
  return index;
}

int remove_zeroes(int a[], int len)
{
  int i;
  for ( ; len > 0; --len)
    if ( a[len-1] > 0 )  break;

  for (i=0; i<len; ++i)
  {
    if (a[i] == 0)
    {
      a[i] = a[len-1];
      --len;
    }    
  }      
  return len;
}

void reminders(int a[], int len, int index)
{
  int i;
  for (i = 0; i<len; ++i)
  {
    if ( i != index)
      a[i] %= a[index];
  }
}

int gcd( int a[], int len)
{

  while ( len > 1)
  {
    int index = index_of_min(a, len);
    if ( a[index] == 1 )
      return 1;
    reminders(a, len, index);
    len = remove_zeroes(a, len);
  }
  return a[0];
}


С образцовыми данными (247, 8645, 1216, 3648), он получает результат за четыре итерации:
247
8645
1216
3648
----
247
190
228
----
57
190
38
----
19
38
----
19
----
result: 19




Полная программа, чтобы ее протестировать:
#include <stdio.h>

void dump( int a[], int len)
{
  int i;
  for (i=0; i<len; ++i)
    printf("%d\n", a[i]);

  printf("----\n");
}

int index_of_min( int a[], int len)
{
  int index = 0;
  int i;
  for ( i=0; i<len; ++i)
  {
    if (a[index] > a[i])
      index = i;
  }
  return index;
}

int remove_zeroes(int a[], int len)
{
  int i;
  for ( ; len > 0; --len)
    if ( a[len-1] > 0 )  break;

  for (i=0; i<len; ++i)
  {
    if (a[i] == 0)
    {
      a[i] = a[len-1];
      --len;
    }
  }      
  return len;
}

void reminders(int a[], int len, int index)
{
  int i; 
  for (i = 0; i<len; ++i)
  {
    if ( i != index)
      a[i] %= a[index];
  }
}

int gcd( int a[], int len)
{

  while ( len > 1)
  { 
    int index = index_of_min(a, len);
    if ( a[index] == 1 )
      return 1;
    reminders(a, len, index);
    len = remove_zeroes(a, len);
    dump(a, len);
  }
  return a[0];
}


int main()
{
  int a[] = {247, 8645, 1216, 3648 };

  int len = sizeof(a) / sizeof(a[0]);

  dump(a, len);

  int result = gcd(a, len);
  if ( result > 0)
    printf("result: %d\n", a[0]);
  else
    printf("no match\n");
  return a[0];
}

PIEBALDconsult

Конечно, вы можете выполнять задачи index_of_min и remove_zeroes в рамках напоминаний.
Нет необходимости перечислять список три раза за итерацию.
При подсчете напоминаний (остатков) следите за индексом мин, а также меняйте местами нули.

CPallini

Хорошая точка. :большой палец вверх:

Jon McKee

{ 5, 7, 20, 40 } разбивает его и возвращает 0 вместо 1. Алгоритм предполагает, что список имеет общий GCD больше 1, когда он может не соответствовать задаче =) EDIT: уточнено "больше 1", 1 - это GCD, как указал пирог =)

CPallini

Ну, я просто неправильно понял требования. Один возврат 1; починил, спасибо.

PIEBALDconsult

Точно; 1-это разумное значение для GCD.

Jon McKee

Особенно учитывая распространенный подход к вычислению LCM, использующий GCD в делителе / знаменателе. 0 не будет Буэно.

CPallini

Ну, это я знаю.
В моем тупом уме я предполагаю, что это было требование (возврат 0, если GCD > 1 не был найден). Я прочитал все изменения требований и могу подтвердить, что нет никаких следов такого costraint. Наверное, мне стоит перестать принимать галлюциногены : - D

Рейтинг:
1

Peter Leow

В этом решении всего три части, читайте их с терпением. :zzz:

+++ + + [Часть 1]+++++

Это поиск грубой силы с помощью следующего алгоритма:

1.  GET a list of integers
1.  SET GCD = 1
2.  SET DIVISOR = 2
3.  WHILE DIVISOR <= the smallest integer
    3.1  Divide each integers by the DIVISOR, starting with the smallest integer and proceed in ascending order 
    3.2  IF ALL divisions result in no remainder 
         3.2.1 SET GCD = DIVISOR
    3.3  DIVISOR = DIVISOR + 1
4.  DISPLAY GCD

Затем реализуйте его в простом старом JavaScript:
var integers = [247, 8645, 1216, 3648];
var gcd = 1;
var divisor = 2;
while(divisor <= integers[0]){
	var isAllDivisible = true;
	for(i=0;i<integers.length;i++){
    	if(integers[i] % divisor != 0){
            isAllDivisible = false;
        	break;
        }
    }
    if(isAllDivisible){
       	gcd = divisor; // continue to search
    }
    divisor++; 
}
alert(gcd);

Edit fiddle - JSFiddle[^]

+++ + + [Часть 2]+++++

Основным недостатком приведенного выше алгоритма поиска грубой силы является то, что он должен исчерпать поиск от 1 до наименьшего целого числа, даже если число оказывается делимым на все целые числа на этом пути.

Лучшим способом будет сделать обратное, то есть начать поиск с наименьшего целого числа и двигаться к нулю, таким образом, первое число, которое окажется делимым на все элементы, будет ответом, и поиск может быть остановлен. Этот способ потенциально может сократить пространство поиска и, как следствие, стать более эффективным. Фрагмент кода показан ниже:
var integers = [247, 8645, 1216, 3648];
var gcd = divisor = Math.min.apply(Math, integers);
while(divisor > 0){
	var isAllDivisible = true;
	for(i=0;i<integers.length;i++){
    	if(integers[i] % divisor != 0){
          isAllDivisible = false;
          break;
        }
    }
    if(isAllDivisible){
       	gcd = divisor; // GCD found and stop searching
        break;
    }
    divisor--; 
}
alert(gcd);

Edit fiddle - JSFiddle[^]

+++ + + [Часть 3]+++++

Это последняя часть. Как насчет того, чтобы попробовать его с помощью некоторых Стохастическая Оптимизация.

Оптимизация-это процесс поиска оптимальных решений для проблем, которые не имеют воспринимаемого способа поиска решений (конечно, эта вещь GCD не является одной из них). Процесс оптимизации развивает оптимальные решения путем поиска случайных решений-кандидатов в пространстве поиска, отсеивая более слабые, но сохраняя более сильные на основе их пригодности. Эволюция продолжается до тех пор, пока не будут выполнены определенные конечные критерии, такие как воспринимаемая оптимальность решений или количество итераций.

Хватит болтать, давайте вернемся к этому вопросу GCD, я разработал алгоритм следующим образом:
First things first, set up the necessary parameters:
search space: lowerBound = 1, upperBound = min(integers) = 247
population size p = 10
candidates  = c0,c1, ...c9
number of iteration i = 10
fitness of candidate = max(candidates) 

The actual optimization process:

1.  Randomly picked a population of candidate GCD's lowerBound <= c0,c1, ...c9  <= upperBound 
2.  Divide each integers with each candidate GCD's 
    r0=247/c0, ... r9=247/c9
    r0=8645/c0, ... r9=8645/c9 
    ...and so on
3.  Discard those candidates that produce non-zero remainders.
4.  Assign the candidate that have the best fitness to be the lowerBound of the search space. (This will reduce the search space and lead to eventual convergence to the optimal solution.)
5.  Rejuvenate the population by replacing candidates that are discarded or fall below the lowerBound.
6.  REPEAT step 2 UNTIL the number of iteration is reached.

Перевод всего этого в JS код:
/*
	Stochastic Optimization in Search of Greatest Common Divisor (GCD)
  By Peter Leow the stochastic coder
*/

var integers = [247, 8645, 1216, 3648];

// Setting parameters
var lowerBound = 1;
var upperBound = Math.min(...integers);
var populationSize = 10; // increase this for better chance
var population = [];
var maxIteration = 20; // increase this for better chance

function generatePopulation(population, populationSize, lowerBound, upperBound) {
  for (var i = 1; i < populationSize; i++) {
    population[i] = Math.floor((Math.random() * upperBound) + lowerBound);
  }
  return population;
}

var desc = ""
population[0] = lowerBound;

for (var i = 0; i < maxIteration; i++) {

  desc += "Iteration: " + (i + 1) + "<br>";
  // Randomly generate candidate GCD's within bound
  population = generatePopulation(population, populationSize, lowerBound, upperBound);
  desc += "Candidates at start: " + population + "<br>";
  // Test candidates and weep out the failure
  for (var j = 0; j < population.length; j++) {
    for (var k = 0; k < integers.length; k++) {
      if (integers[k] % population[j] != 0) {
        population.splice(j, 1); // remove failed candidate from the population
        j--;
        break; // and break out!
      }
    }
  }
  desc += "Candidates left: " + population + "<br>";
  // Find the new lower bound of the search space
  if (population.length != 0) {
    lowerBound = Math.max(...population);
    population = [];
    population[0] = lowerBound;
  }
  desc += "Best candidate so far: " + lowerBound + "<br>";
  desc += "====================================" + "<br>";
}

document.getElementById("desc").innerHTML = desc;

И HTML-тег для отображения прогресса и результата:
<div id="desc"></div>

Edit fiddle - JSFiddle[^]

Запустите его, и вы можете не получить правильный ответ 19, запустите его несколько раз, вы должны получить его. Если вы увеличите количество итераций или размер популяции, шансы получить правильный ответ на проблему GCD также возрастут. Мельком взгляните на пример запуска в течение 20 итераций:
Iteration: 1
Candidates at start: 1,213,240,185,219,247,207,216,160,179
Candidates left: 1
Best candidate so far: 1
====================================
Iteration: 2
Candidates at start: 1,125,159,51,177,154,134,149,78,64
Candidates left: 1
Best candidate so far: 1
====================================
Iteration: 3
Candidates at start: 1,84,153,237,234,52,5,24,43,23
Candidates left: 1
Best candidate so far: 1
====================================
Iteration: 4
Candidates at start: 1,9,195,181,46,228,14,84,235,129
Candidates left: 1
Best candidate so far: 1
====================================
Iteration: 5
Candidates at start: 1,103,241,72,22,44,30,166,109,203
Candidates left: 1
Best candidate so far: 1
====================================
Iteration: 6
Candidates at start: 1,174,4,235,3,205,23,199,190,181
Candidates left: 1
Best candidate so far: 1
====================================
Iteration: 7
Candidates at start: 1,53,139,131,180,180,222,128,181,45
Candidates left: 1
Best candidate so far: 1
====================================
Iteration: 8
Candidates at start: 1,31,136,55,168,218,101,51,94,48
Candidates left: 1
Best candidate so far: 1
====================================
Iteration: 9
Candidates at start: 1,127,133,136,19,121,171,6,96,200
Candidates left: 1,19
Best candidate so far: 19
====================================
Iteration: 10
Candidates at start: 19,65,204,241,222,63,56,116,141,38
Candidates left: 19
Best candidate so far: 19
====================================
Iteration: 11
Candidates at start: 19,47,225,41,199,222,226,239,109,209
Candidates left: 19
Best candidate so far: 19
====================================
Iteration: 12
Candidates at start: 19,243,32,120,243,25,132,168,191,235
Candidates left: 19
Best candidate so far: 19
====================================
Iteration: 13
Candidates at start: 19,218,162,78,170,159,215,137,193,165
Candidates left: 19
Best candidate so far: 19
====================================
Iteration: 14
Candidates at start: 19,141,263,247,94,49,216,146,135,181
Candidates left: 19
Best candidate so far: 19
====================================
Iteration: 15
Candidates at start: 19,224,128,252,93,48,248,172,110,78
Candidates left: 19
Best candidate so far: 19
====================================
Iteration: 16
Candidates at start: 19,48,155,179,258,190,221,142,70,48
Candidates left: 19
Best candidate so far: 19
====================================
Iteration: 17
Candidates at start: 19,51,81,231,21,135,219,93,245,124
Candidates left: 19
Best candidate so far: 19
====================================
Iteration: 18
Candidates at start: 19,81,102,46,123,166,68,159,203,239
Candidates left: 19
Best candidate so far: 19
====================================
Iteration: 19
Candidates at start: 19,203,123,219,44,24,56,200,35,226
Candidates left: 19
Best candidate so far: 19
====================================
Iteration: 20
Candidates at start: 19,129,152,22,205,248,174,131,44,121
Candidates left: 19
Best candidate so far: 19
====================================

Вы только что узнали, что решения, предлагаемые оптимизацией, могут отличаться. Заметим, что качество решений, получаемых в результате оптимизации, будет зависеть от многих факторов, некоторые из которых-размер популяции и количество итераций.

Все доро

F-ES Sitecore

Евклид будет крутиться в могиле!

PIEBALDconsult

Неужели ему нужно было обрабатывать сразу 500 предметов?

Patrice T

Боюсь, он повернулся к фану.

Mohibur Rashid

Понравилось !

Peter Leow

Он должен быть счастлив до тех пор, пока это служит предметом спора, который стимулирует более инновационные решения. Я вижу, что это уже произошло. Ура!

PIEBALDconsult

Вы можете попробовать использовать только простые числа в качестве делителей.

Patrice T

Уважаемый Петр,
существуют гораздо более эффективные алгоритмы.

Рейтинг:
1

Jon McKee

РЕДАКТИРОВАТЬ: Обновил свой алгоритм, чтобы разрешить загрузку для этой задачи. Теперь гораздо лучше (результаты опубликованы в конце).

Это было весело. Я уже знал о двоичном евклидовом алгоритме, так как мне уже приходилось вычислять GCDs раньше. Поэтому, чтобы добавить свою собственную уникальность к этой проблеме, я решил разработать способ параллельного выполнения задачи, поскольку рекурсивный двоичный евклидов алгоритм на самом деле не дает много места для уникальности (каждый путь, кроме одного, является хвостовым вызовом, поэтому оптимизируется в JMP).

public static class GCD
{
    public static uint CalculateParallel(List<uint> numbers, int taskLoad)
    {
        int totalTasks = numbers.Count / taskLoad;
        Task<uint>[] gcdTasks = new Task<uint>[totalTasks];
        for (int i = 0; i < totalTasks; i++)
        {
            int startIndex = i * taskLoad;
            gcdTasks[i] = Task.Run(() => 
                CalculateGCDForRange(numbers, startIndex, taskLoad));
        }

        uint gcd = 0;
        int remainingNumbers = numbers.Count % taskLoad;
        if (remainingNumbers > 0)
            gcd = CalculateGCDForRange(numbers, totalTasks * taskLoad,
                                       remainingNumbers);

        Task.WaitAll(gcdTasks);
        foreach (Task<uint> task in gcdTasks)
            gcd = BinaryEuclidGCD(gcd, task.Result);
        return gcd;
    }

    public static uint CalculateGCDForRange(List<uint> numbers, int startIndex, int count)
    {
        uint gcd = numbers[startIndex];
        for (; count > 1; count--)
            gcd = BinaryEuclidGCD(gcd, numbers[++startIndex]);
        return gcd;
    }

    public static uint BinaryEuclidGCD(uint firstNumber, uint secondNumber)
    {
        if (firstNumber == 0)
            return secondNumber;
        if (secondNumber == 0 || firstNumber == secondNumber)
            return firstNumber;

        //Cases where at least one number is even
        if ((firstNumber & 1) == 0)
        {
            if ((secondNumber & 1) == 0)
                return BinaryEuclidGCD(firstNumber >> 1, secondNumber >> 1) << 1;
            else
                return BinaryEuclidGCD(firstNumber >> 1, secondNumber);
        }
        if ((secondNumber & 1) == 0)
            return BinaryEuclidGCD(firstNumber, secondNumber >> 1);

        //Cases where both numbers are odd
        if (firstNumber > secondNumber)
            return BinaryEuclidGCD((firstNumber - secondNumber) >> 1, secondNumber);
        return BinaryEuclidGCD((secondNumber - firstNumber) >> 1, firstNumber);
    }
}


Тест:
static void Main(string[] args)
{
    List<uint> numbers = GenerateList(3571, 1000000);
    Stopwatch sw = new Stopwatch();
    sw.Start();
    uint result = GCD.CalculateGCDForRange(numbers, 0, numbers.Count);
    sw.Stop();
    Console.WriteLine($"Sequential GCD: {result}");
    Console.WriteLine($"Time (ms): {sw.ElapsedMilliseconds}");
    sw.Reset();
    sw.Start();
    result = GCD.CalculateParallel(numbers, 10000);
    sw.Stop();
    Console.WriteLine($"Parallel GCD: {result}");
    Console.WriteLine($"Time (ms): {sw.ElapsedMilliseconds}");
    Console.ReadKey();
}

//Accepts a seed value up to 3571, the 500th prime.  Past that will be out
//of range for a uint unless a smaller maxRange is specified.
private static List<uint> GenerateList(int seed, int count, int maxRange = 1200000)
{
    List<uint> values = new List<uint>(count);
    Random rnd = new Random();
    for (; count > 0; count--)
        values.Add((uint)(seed * rnd.Next(maxRange)));
    return values;
}


обновленные результаты: Запустив 1 000 000 чисел с GCD 3571 я получаю следующие результаты:
Sequential GCD: 3571
Time (ms): 523

Parallel GCD: 3571
Time (ms): 158

Рейтинг:
1

Mohibur Rashid

еще один пример c(не ожидая, что он будет самым лучшим)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int get_smallest_number(int *array, int length) {
    int *arr=array;
    int small=arr[0];
    int i;
    for(i=1;i<length; i++) {
        if(small>arr[i]) {
            small=arr[i];
        }
    }
    for(i=0;i<length;i++){
        if(arr[i]==small){
            arr[i]=0;
        }
    }
    return small;
}

int get_all_divisor(int number, int *to_ret) {
    int i;
    int *to_ret_ref=to_ret;
    int count=1;
    to_ret_ref[0] = 1;
    for(i=2;i<=number/2;i++) {
        if(number%i==0) {
            to_ret_ref[count] = i;
            count++;
        }
    }
    to_ret_ref[count] = number;
    count++;
    return count;
}
int gcd(int *numbers, int length_number, int *divisors, int lengt_divi) {
    int i, j;
    for(i=0;i<length_number;i++) {
        if(numbers[i]!=0) {
            for(j=lengt_divi-1;j>=0;j--){
                if(divisors[j]!=0 && numbers[i]%divisors[j]!=0){
                    divisors[j]=0;
                }
            }
        }
    }
    for(j=lengt_divi-1;j>=0;j--) {
        if(divisors[j]!=0) {
            return divisors[j];
        }
    }
    return -1;
}
int main(int args, char **argv) {
    int i;
    int *arr=malloc((args-1) * sizeof(int));
    int smallest, divisor_count;
    int *divisors;
    for(i=1;i<args; i++){
        arr[i-1] = abs(atoi(argv[i]));
    }

    smallest=get_smallest_number(arr, args-1);
    if (smallest == 1) {
        printf("1\n");
        return 0;
     }
     divisors=malloc(((int)(smallest/2) + 1) * sizeof(int));
     divisor_count=get_all_divisor(smallest, divisors);
     printf("%d\n", gcd(arr, args-1, divisors, divisor_count));
     free(arr);
     free(divisors);
     return 0;
 }

Рейтинг:
0

Patrice T

Язык: Clipper/xHarbour

clear
? "CCCP Code Chalenge Code Project"
? "GCD"
lst= {247, 8645, 1216, 3648}
ans= gcd(lst)
? ans
return

function gcd(lst)
	b= lst[1]
	for scan=2 to len(lst)
		a= lst[scan]
		while (tmp:=a%b) != 0
			a= b
			b= tmp
		enddo
	next
	return b

Я старался быть как можно прямее
Возьмите первые 2 числа и вычислите их GCD.
Возьмите первое ГКД и третье число и вычислите их ГКД.
И так до самого конца.

Рейтинг:
0

Graeme_Grant

Благодаря Петр Leow[^] для получения удовольствия от поиска решения. Хотя у него есть интересное решение, я подумал, что есть гораздо более быстрый способ сделать это.

Мне нравится быстрый код, и пока я не изобрел алгоритм "двоичного наибольшего общего делителя" (оригинальная версия C для 2 значений, найденных здесь...), Я поместил свою собственную слегка улучшенную версию C# ниже.

using System;
using System.Linq;

namespace GCD
{
    class Program
    {
        static void Main(string[] args)
        {
            var values = new[] { 247, 8645, 0, -1216, 3648 };
            Console.WriteLine("Greatest Common Denominator - Binary version");
            Console.WriteLine("");
            Console.WriteLine($"Given:   {string.Join(", ", (values))}");
            Console.WriteLine($"Returns: {gcd(values)}");
            Console.WriteLine("");
            Console.WriteLine("-- Press any key --");
            Console.ReadKey();
        }

        public static int gcd(int[] x)
        {
            if (x.Length < 2)
                throw new ArgumentException("More than 2 number required.");

            // check for negatives and zero values - as suggested by PIEBALDconsult
            x = x.Where(n => n != 0).Select(n => n < 0 ? -n : n).ToArray();

            int v = gcd(x[x.Length - 1], x[x.Length - 2]);
            for (int i = x.Length - 3; i >= 0; i--)
                v = gcd(v, x[i]);

            return v;
        }

        private static int gcd(int u, int v) 
            => (int) gcd((uint) u, (uint) v);

        private static uint gcd(uint u, uint v)
        {
            int shift;
            if (u == 0) return v;
            if (v == 0) return u;

            shift = ctzb(u | v);
            u >>= ctzb(u);

            do
            {
                v >>= ctzb(v);
                if (u > v) Swap(ref v, ref u);
                v = v - u;
            } while (v != 0);

            return u << shift;
        }

        // Count trailing zero bits
        private static int ctzb(uint x)
        {
            int n = 1;
            if ((x & 0x0000FFFF) == 0)
            {
                n += 16;
                x >>= 16;
            }
            if ((x & 0x000000FF) == 0)
            {
                n += 8;
                x >>= 8;
            }
            if ((x & 0x0000000F) == 0)
            {
                n += 4;
                x >>= 4;
            }
            if ((x & 0x00000003) == 0)
            {
                n += 2;
                x >>= 2;
            }
            return (int) (n - (x & 1));
        }

        public static void Swap<T>(ref T lhs, ref T rhs)
        {
            T temp = lhs;
            lhs = rhs;
            rhs = temp;
        }
    }
}


И выход:

Greatest Common Denominator - Binary version

Given:   247, 8645, 0, -1216, 3648
Returns: 19

-- Press any key --


ОБНОВЛЕНИЕ: Я решил вернуться к своим корням и создать VB.Чистая версия также...

Module Module1

    Sub Main()

			Dim values() = { 247, 8645, 0, -1216, 3648 }

			Console.WriteLine("Greatest Common Denominator - Binary version")
			Console.WriteLine("")
			Console.WriteLine($"Given:   {string.Join(", ", (values))}")
			Console.WriteLine($"Returns: {gcd(values)}")
			Console.WriteLine("")
			Console.WriteLine("-- Press any key --")
			Console.ReadKey()

	End Sub

	Public Function gcd(x As Integer()) As Integer

		If x.Length < 2 Then
			Throw New ArgumentException("More than 2 number required.")
		End If

		' test and adjust for negatives/zero values
		x = x.Where(Function(n) n <> 0).Select(Function(n) If(n < 0, -n, n)).ToArray()

		Dim v As Integer = gcd(x(x.Length - 1), x(x.Length - 2))
		For i As Integer = x.Length - 3 To 0 Step -1
			v = gcd(v, x(i))
		Next

		Return v

	End Function

	Private Function gcd(u As Integer, v As Integer) As Integer
		Return gcd(CUInt(u), CUInt(v))
	End Function

	Private Function gcd(u As UInteger, v As UInteger) As UInteger

		Dim shift As Integer
		If u = 0 Then Return v
		If v = 0 Then Return u

		shift = ctzb(u Or v)
		u >>= ctzb(u)

		Do
			v >>= ctzb(v)
			If u > v Then Swap(v, u)
			v = v - u
		Loop While v <> 0

		Return u << shift

	End Function

	' Count trailing zero bits
	Private Function ctzb(x As UInteger) As Integer

		Dim n As Integer = 1
		If (x And &Hffff) = 0 Then
			n += 16
			x >>= 16
		End If
		If (x And &Hff) = 0 Then
			n += 8
			x >>= 8
		End If
		If (x And &Hf) = 0 Then
			n += 4
			x >>= 4
		End If
		If (x And &H3) = 0 Then
			n += 2
			x >>= 2
		End If

		Return n - (x And 1)

	End Function

	Public Sub Swap(Of T)(ByRef lhs As T, ByRef rhs As T)

		Dim temp As T = lhs
		lhs = rhs
		rhs = temp

	End Sub

End module

PIEBALDconsult

Почему все числа должны быть положительными? Шахта работает как на негативы, так и на ноль.
А как насчет списка из одного пункта?

Graeme_Grant

Не было ни запроса на негативы, ни их проверки.

Кстати, вы публиковали пост перед тем, как критиковать других?

PIEBALDconsult

- Пока нет. Мой код не очень интересен, очень похож на рабочий. Скорее всего, я опубликую его позже в качестве анти-примера.

Graeme_Grant

Аааа, понятно.

Обычно я такой же, но, похоже, чистый код не является целью этих упражнений...

Graeme_Grant

Я мог бы добавить препроцессор для переворачивания отрицательных входных значений... Как для одного номера, нет ГКД... только ГД.

Graeme_Grant

Для полноты картины я обновил решение для вас PIEBALDconsult, включив в него 0 и отрицательные значения. :)

PIEBALDconsult

Благодарю вас. Элвис благодарит тебя. Элвис очень Вам благодарен.

Рейтинг:
0

PIEBALDconsult

Я делать у меня есть реализации GCD с использованием алгоритмов Евклида и двоичных алгоритмов - только для двух операндов, - но я решил их не использовать.
Итак, вот простой (возможно, второкурсник) метод, который уменьшит значения в списке и вернуться НОД.

Он работает для отрицательных значений, нулей и одноэлементных входных списков.

Factor должен быть список простых чисел в порядке возрастания, с достаточным диапазоном для факторизации входного значения наименьшей величины (ближайшего к нулю).

public static int
Reduce
(
  System.Collections.Generic.IList<int> List
,
  System.Collections.Generic.IList<int> Factor
)
{
  /* Add checks for null and empty as desired. */

  int result = 1 ;

  int least = System.Math.Abs ( List [ 0 ] ) ;

  for ( int i = 1 ; i < List.Count ; i++ )
  {
    if ( least > System.Math.Abs ( List [ i ] ) )
    {
      least = System.Math.Abs ( List [ i ] ) ;
    }
  }

  int f = 0 ;

  while ( ( f < Factor.Count ) && ( least >= Factor [ f ] ) )
  {
    int i = 0 ;

    while ( ( i < List.Count ) && ( List [ i ] % Factor [ f ] == 0 ) )
    {
      i++ ;
    }

    if ( i == List.Count )
    {
      result *= Factor [ f ] ;

      least /= Factor [ f ] ;

      for ( i = 0 ; i < List.Count ; i++ )
      {
        List [ i ] /= Factor [ f ] ;
      }
    }
    else
    {
      f++ ;
    }
  }

  return ( result ) ;
}


Для удобства тестирования приведем список первых ста простых чисел:

Primes = ( new System.Collections.Generic.List<int>
( new int[]
{
    2 ,   3 ,   5 ,   7 ,  11 ,  13 ,  17 ,  19 ,  23 ,  29 ,
   31 ,  37 ,  41 ,  43 ,  47 ,  53 ,  59 ,  61 ,  67 ,  71 ,
   73 ,  79 ,  83 ,  89 ,  97 , 101 , 103 , 107 , 109 , 113 ,
  127 , 131 , 137 , 139 , 149 , 151 , 157 , 163 , 167 , 173 ,
  179 , 181 , 191 , 193 , 197 , 199 , 211 , 223 , 227 , 229 ,
  233 , 239 , 241 , 251 , 257 , 263 , 269 , 271 , 277 , 281 ,
  283 , 293 , 307 , 311 , 313 , 317 , 331 , 337 , 347 , 349 ,
  353 , 359 , 367 , 373 , 379 , 383 , 389 , 397 , 401 , 409 ,
  419 , 421 , 431 , 433 , 439 , 443 , 449 , 457 , 461 , 463 ,
  467 , 479 , 487 , 491 , 499 , 503 , 509 , 521 , 523 , 541
} ) ).AsReadOnly() ;