Archetypical Example: Euclid's Method of Computing Greatest Common Divisors 超典型的ソースコードの見本~最大公約数を計算する、ユークリッドの互除法

形式
C
投稿日時
2015-03-31 14:48
公開期間
無期限
  1. /* A little algorithmic adventure in math,
  2. // Greatest common denominator/divisor.
  3. //
  4. // Note that this does not attempt to properly handle negative numbers
  5. // beyond what strtoul() does.
  6. // (When did strtoul() start "casting" negatives to positive?)
  7. //
  8. // If anyone hassles me about Intellectual Property on this,
  9. // I'll hit them over the head with a copy of Euclid, and again with a copy of Knuth.
  10. // Joel Rees, Amagasaki, March 2015
  11. */
  12. #include <stdio.h>
  13. #include <stdlib.h>
  14. long gcd( long numA, long numB )
  15. {
  16. long temp;
  17. while ( numA != numB )
  18. {
  19. if ( numA < numB )
  20. {
  21. temp = numA;
  22. numA = numB;
  23. numB = temp;
  24. }
  25. numA -= numB;
  26. }
  27. return numA;
  28. }
  29. int main( int argc, char * argv[] )
  30. {
  31. long n1, n2;
  32. char * parseP;
  33. long divisor;
  34. if ( argc != 3 )
  35. { printf( "usage: %s <numA> <numB>\n",
  36. argv[ 0 ] );
  37. puts( "\tto calculate the greatest common divisor\n\tof two unsigned numbers." );
  38. return EXIT_FAILURE;
  39. }
  40. n1 = strtoul( argv[ 1 ], &parseP, 0 );
  41. if ( parseP > argv[ 1 ] )
  42. {
  43. n2 = strtoul( argv[ 2 ], &parseP, 0 );
  44. if ( parseP > argv[ 2 ] )
  45. {
  46. divisor = gcd( n1, n2 );
  47. printf( "greatest common divisor: %ld\n", divisor );
  48. printf( "%ld/%ld => %ld/%ld\n", n1, n2, n1 / divisor, n2 / divisor );
  49. return EXIT_SUCCESS;
  50. }
  51. else
  52. {
  53. printf( "%s is not an unsigned number I can recognize.\n", argv[ 2 ] );
  54. }
  55. }
  56. else
  57. {
  58. printf( "%s is not an unsigned number I can recognize.\n", argv[ 1 ] );
  59. }
  60. return EXIT_FAILURE;
  61. }
ダウンロード 印刷用表示

このコピペの URL

JavaScript での埋め込み

iframe での埋め込み

元のテキスト