匿名使用者
匿名使用者 發問時間: 電腦與網際網路程式設計 · 2 個月前

要如何用c語言把輾轉相除法跟短除法做出來?

如標題,要輸出出來的時候要像這樣,謝謝

Attachment image

1 個解答

評分
  • 2 個月前
    最佳解答

    #include<stdio.h>

    unsigned gcd(

      unsigned a,

      unsigned b

    ){

      switch(a){

      case 0: return b ? b : 1;

      case 1: return 1;

      }

      return gcd(b%a, a);

    }

    int main(){

      unsigned a[2], ans;

      for(

         ; printf("Choose 1. find GCD. 2. find LCM. : ")

        && scanf ("%u", &ans)

        && (1 == ans || 2 == ans)

        && printf("Give me the first number :")

        && scanf ("%u", &a[0])

        && printf("Give me the second number :")

        && scanf ("%u", &a[1])

         ;){

        unsigned gcdy, m[2]={0};

        switch(ans){

        case 1:

        for( ans = a[0] > a[1]

           ; a[0]

          && a[1]

           ; ans = a[0] > a[1]

           ){

          unsigned d[2]={0}, r[2]={0};

          gcdy    = a[ans];

          d[!ans] = a[!ans]/gcdy;

          m[!ans] = d[!ans]*gcdy;

          gcdy    =

          r[!ans] = a[!ans] - m[!ans];

          if(gcdy) {

            d[ans] = a[ans]/gcdy;

            m[ans] = d[ans]*gcdy;

            r[ans] = a[ans]-m[ ans];

          } else {

            r[ans] =

            d[ans] =

            m[ans] = 0;

            gcdy   = a[ans];

          }

          if(d[0]) printf("%6u ", d[0]);

          else     printf("       ");

          printf("| %6u | %6u ", a[0], a[1]);

          if(d[1]) printf("| %6u\n       ", d[1]);

          else     printf("| \n       ");

          if(m[0]) printf("| %6u ", m[0]);

          else     printf("|        ");

          if(m[1]) printf("| %6u |\n", m[1]);

          else     printf("|        |\n");

          if(m[0]) printf("       |--------");

          else     printf("       |        ");

          if(m[1]) printf("|--------|\n");

          else     printf("|        |\n");

          a[0] = r[0], a[1] = r[1];

        }

        if(m[0]) printf("%15u",  a[0]);

        else     printf("               ");

        if(m[1]) printf("%9u\n", a[1]);

        else     printf("\n");

        printf("GCD is %u.\n", gcdy);

        break;

        case 2:{

          unsigned gcdx = gcd(a[0], a[1]);

          printf("%6u | %6u %6u\n", gcdx, a[0], a[1]);

          printf("%6s +-%6s-%6s--\n", "      ", "------", "------");

          printf("%6s   %6u %6u  \n", "      ", a[0]/gcdx,a[1]/gcdx);

          printf("LCM of %u and %u is %u.\n", a[0], a[1], a[0]*a[1]/gcdx);

        } break;

        }

      }

      return 0;

    }

    ~/Projects/C$ gcc -o gcd gcd.c -Wall -O3 -ansi

    ~/Projects/C$ ./gcd

    Choose 1. find GCD. 2. find LCM. : 1

    Give me the first number :345

    Give me the second number :453

         3 |    345 |    453 |      1

            |    324 |    345 |

            |--------|--------|

         7 |     21 |    108 |      5

            |     21 |    105 |

            |--------|--------|

                  0        3

    GCD is 3.

    Choose 1. find GCD. 2. find LCM. : 1

    Give me the first number :99375

    Give me the second number :66543

         1 |  99375 |  66543 |      2

           |  66543 |  65664 |

           |--------|--------|

        37 |  32832 |    879 |      2

             |  32523 |    618 |

           |--------|--------|

         1 |    309 |    261 |      5

           |    261 |    240 |

           |--------|--------|

         2 |     48 |     21 |      3

           |     42 |     18 |

           |--------|--------|

         2 |      6 |      3 |

           |      6 |        |

           |--------|        |

                  0

    GCD is 3.

    Choose 1. find GCD. 2. find LCM. : 1

    Give me the first number :66543

    Give me the second number :99375

         2 |  66543 |  99375 |      1

           |  65664 |  66543 |

           |--------|--------|

         2 |    879 |  32832 |     37

           |    618 |  32523 |

           |--------|--------|

         5 |    261 |    309 |      1

           |    240 |    261 |

           |--------|--------|

         3 |     21 |     48 |      2

           |     18 |     42 |

           |--------|--------|

           |      3 |      6 |

       2       |        |      6 |

           |        |--------|

                           0

    GCD is 3.

    Choose 1. find GCD. 2. find LCM. : 0

    ~/Projects/C$

還有問題?馬上發問,尋求解答。