A001_Euclid

유클리드의 최대공약수 알고리즘을 작성해보았다.

우선, 최대공약수는 2개 이상의 자연수의 공약수들 중에서 가장 큰 수이다.

유클리드는 2개의 자연수의 최대공약수는 큰 수에서 작은 수를 뺀 수와 작은 수와의 최대공약수와 같다는 성질을 이용하여 최대 공약수를 찾았다. 여기에서 나온 것이 바로 유클리드의 최대공약수 알고리즘이다. 

유클리드의 최대공약수 알고리즘에서는 뺄셈 대신에 나눗셈을 사용하면 빠르게 해를 찾을 수 있다.

---

다음은 MainWindow이다.

txtBlock 2개 -> txtBlock,txtResult
txtBox 2개 -> txtNo1, txtNo2
button 1개 ->button

 

다음은 MainWindow의 코드이다.

<Window x:Class="A001_Euclid.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
        xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
        xmlns:local="clr-namespace:A001_Euclid"
        mc:Ignorable="d"
        Title="MainWindow" Height="305" Width="512">
    <Grid Margin="0,0,0,3" HorizontalAlignment="Center" Width="512">
        <Grid.ColumnDefinitions>
            <ColumnDefinition/>
            <ColumnDefinition Width="0*"/>
        </Grid.ColumnDefinitions>
        <TextBlock x:Name="textBlock" HorizontalAlignment="Left" Margin="61,73,0,0" Text="Euclid 최대공약수 알고리즘" TextWrapping="Wrap" VerticalAlignment="Top" Height="16" Width="189"/>
        <TextBox x:Name="txtNo1" HorizontalAlignment="Left" Margin="61,125,0,0" TextWrapping="Wrap" VerticalAlignment="Top" Width="120" Height="18"/>
        <TextBox x:Name="txtNo2" HorizontalAlignment="Left" Margin="209,125,0,0" TextWrapping="Wrap" VerticalAlignment="Top" Width="120" Height="18"/>
        <Button x:Name="button" Content="Find!" HorizontalAlignment="Left" Margin="361,125,0,0" VerticalAlignment="Top" Width="75" Height="20" Click="button_Click"/>
        <TextBlock x:Name="txtResult" HorizontalAlignment="Left" Margin="61,201,0,0" Text="최대공약수는?" TextWrapping="Wrap" VerticalAlignment="Top" Height="16" Width="260"/>

    </Grid>
</Window>

 

MainWindow에서 button을 클릭시 유클리드 알고리즘이 실행되게 코드를 짜보았다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;

// Euclid algorithm - GCD
namespace A001_Euclid
{
  /// <summary>
  /// Interaction logic for MainWindow.xaml
  /// </summary>
  public partial class MainWindow : Window
  {
    public MainWindow()
    {
      InitializeComponent();
    }

    private void button_Click(object sender, RoutedEventArgs e)
    {
      int x = int.Parse(txtNo1.Text);
      int y = int.Parse(txtNo2.Text);
      int gcd = Euclid(x, y);
      txtResult.Text = "최대공약수 = " + gcd.ToString();
    }

    private int Euclid(int x, int y)
    {
      if (y == 0)
        return x;
      else
        return Euclid(y, x % y);
    }
  }
}

 

버튼을 클릭 했을 때 코드이다.

private void button_Click(object sender, RoutedEventArgs e)
    {
      int x = int.Parse(txtNo1.Text);
      int y = int.Parse(txtNo2.Text);
      int gcd = Euclid(x, y);
      txtResult.Text = "최대공약수 = " + gcd.ToString();
    }

3~4 버튼을 클릭했을 때 txtNo1의 입력된 값은 int x에 txtNo2의 입력된 값은 int y에 저장된다.

5 유클리드 코드를 만들어 gcd에 저장되게 한다.

6 txtResult에 최대공약수 = gcd가 뜨게 한다.

 

private int Euclid(int x, int y)
    {
      if (y == 0)
        return x;
      else
        return Euclid(y, x % y);
    }

유클리드 함수이다. y가 0이라면 리턴하고 아니라면 유클리드 공식을 작성해준다. 

 

다음 밑에 화면은 실행화면이다.