İki Nömrənin GCD

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Nədir Ən böyük ümumi amil? İki rəqəmin GCD, ikisini də bölən ən böyük rəqəmdir.

Yanaşma-1

Brute Force

Bütün tapmaq baş hər iki ədədin amilləri, daha sonra kəsişmənin məhsulunu tapın.

Hər iki ədədi bölən ən böyük ədədi tapmaq.

Eyni şey üçün etdiyimiz nədir?

• İki rəqəmdən kiçikini tapın
  • Niyə?
  • Nümunə-4,6.
    • Ən böyük əsas amil 6-dən az olanda 4-nın bütün amillərini hesablamağın heç bir mənası yoxdur
• 1-dən daha kiçik rəqəmə bir döngə aparın
• Cavabını saxlamaq üçün dəyişən saxla
• Bir rəqəm hər iki rəqəmi bölürsə, dəyişəni sadəcə yeniləyirik

Kiçik prosesi izləyin və hər iki rəqəmin ən böyük əsas amili ilə nəticələnin!

Yenə də ağılsız? Kodu nəzərdən keçirin!

İki Nömrənin GCD-si üçün Java Kodu

import java.util.*;
public class GCD
{
  public static int find_fac(int num1,int num2)
  {
    int ans=1;
    int num=0;
    if(num1>num2)
      num=num2;
    else
      num=num1;
    for(int i=num;i>0;i--)
    {
      if(num1%i==0 && num2%i==0)
      {ans=i;break;}
    }
    return ans;
  }
  public static void main(String args[])
  {
    int gcd=find_fac(12,28);
    System.out.println(gcd);
  }
}

İki Nömrənin GCD-si üçün C ++ Kodu

#include<iostream>
using namespace std;
int find_fac(int num1,int num2)
{
  int ans=1; 
  int num=0; 
  if(num1>num2) 
    num=num2; 
  else 
    num=num1; 
  for(int i=num;i>0;i--) 
  { 
    if(num1%i==0 && num2%i==0) 
      {ans=i;break;} 
  } 
  return ans;
}
int main()
{
  int gcd=find_fac(12,28);
  cout<<gcd;
}

4

İki Nömrənin GCD üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi = O (n)

Yanaşma-2

GCD üçün Öklid alqoritmindən istifadə

Alqoritm Prinsipinə görə: HCF kiçikdən daha çox say çıxmaqla dəyişmir.

Təkrar Çıxarma = Bölmə olduğunu bilirik

Eyni problemlə ağıllı olmaq üçün üç qızıl qaydaya əməl edilməlidir.

Onları başınıza sığdırın və nüvənə qədər anlayın!

• GCD (a, b) = GCD (b, a) əgər b> a
• GCD (a, b) = GCD (a, a% b)
• GCD (a, 0) = a

Bir dəfəyə götürməyiniz bu çox olsa, narahat olmayın, sizin üçün kiçik bir sxem sxemim var.

Pin

Blok sxemindəki nümunə - (10,14)

• GCD-ni (14,10) 14> 10 olaraq tapırıq
  • GCD (14,10) = GCD (14% 10,10)
• (4,10) GCD-nin hesablanması üçün işləyin
• (10,4) HCF 10> 4 olaraq hesablanacaqdır
  • HCF (10,4) = GCD (10% 4,4) = GCD (2,4)
• GCD-ni (4,2) 4> 2 olaraq tapın
  • HCF (4,2) = GCD (4% 2,2) = GCD (2,2)
• GCD (2,2) = HCF (0,2)
• 0.Voilaya vurduğumuz kimi cavabımız var! 2

GCD Of Two Numbers üçün Java proqramı

import java.util.*;
public class GCD
{
  public static int find_fac(int num1,int num2)
  {
    if(num2==0)
      return num1;
    if(num1>num2)
      return find_fac(num1%num2,num2);
    else
      return find_fac(num2,num1);
  }
  public static void main(String args[])
  {
    int gcd=find_fac(12,24);
    System.out.println(gcd);
  }
}

İki Nömrənin GCD-si üçün C ++ Kodu

#include<iostream>
using namespace std;
int find_fac(int num1,int num2)
{
  if(num2==0)
      return num1;
  if(num1>num2)
      return find_fac(num1%num2,num2);
  else
      return find_fac(num2,num1);
}
int main()
{
  int gcd=find_fac(12,24);
  cout<<gcd;
}

12

İki Nömrənin GCD üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi = O (log (n))

N hər iki ədədin minimumudur

Bunlar rəqəmlərin HCF-sini tapmağın yolları idi!

Bir problemə dair bacarıqları çevirsək və daha mürəkkəb şeylər öyrənsək?

Eratosfen ələyi!

Eratosthenlərin ələk