{"id":550,"date":"2013-01-03T04:58:08","date_gmt":"2013-01-02T19:58:08","guid":{"rendered":"http:\/\/yucchi.jp\/blog\/?p=550"},"modified":"2013-04-24T21:59:32","modified_gmt":"2013-04-24T12:59:32","slug":"%e3%83%a6%e3%83%bc%e3%82%af%e3%83%aa%e3%83%83%e3%83%89%e3%81%ae%e4%ba%92%e9%99%a4%e6%b3%95-euclidean-algorithm","status":"publish","type":"post","link":"http:\/\/yucchi.jp\/blog\/?p=550","title":{"rendered":"\u30e6\u30fc\u30af\u30ea\u30c3\u30c9\u306e\u4e92\u9664\u6cd5 Euclidean Algorithm"},"content":{"rendered":"<p>Java \u3067\u30e6\u30fc\u30af\u30ea\u30c3\u30c9\u306e\u4e92\u9664\u6cd5\u3000Euclidean Algorithm \u3092\u30d7\u30ed\u30b0\u30e9\u30df\u30f3\u30b0\u3057\u3066\u307f\u307e\u3057\u305f\u3002<\/p>\n<p>\u518d\u5e30\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u4f7f\u3063\u3066\u307e\u3059\u3002<\/p>\n<p>\u518d\u5e30\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306b\u3064\u3044\u3066\u306f\u3053\u3061\u3089\u3067\u7c21\u5358\u306a\u899a\u3048\u66f8\u304d\u3092\u6b8b\u3057\u3066\u3042\u308a\u307e\u3059\u3002<\/p>\n<p><a href=\"http:\/\/yucchi.jp\/blog\/?p=538\">\u518d\u5e30\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3000\u305d\u306e\uff11<\/a><\/p>\n<p><a href=\"http:\/\/yucchi.jp\/blog\/?p=544\" target=\"_blank\">\u518d\u5e30\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3000\u305d\u306e\uff12<\/a><\/p>\n<p>\u30e6\u30fc\u30af\u30ea\u30c3\u30c9\u306e\u4e92\u9664\u6cd5\u3068\u306f\u3044\u3063\u305f\u3044\u3069\u3093\u306a\u4ed5\u7d44\u307f\u306a\u306e\u304b\u8abf\u3079\u3066\u307f\u307e\u3057\u305f\u3002<\/p>\n<p>\u3042\u308b\u4e8c\u3064\u306e\u81ea\u7136\u6570\u306e\u6700\u5927\u516c\u7d04\u6570\u3092\u6c42\u3081\u308b\u306e\u306b\u975e\u5e38\u306b\u512a\u308c\u305f\u65b9\u6cd5\u3089\u3057\u3044\u3067\u3059\u3002<\/p>\n<p>\u540d\u524d\u306b\u4e92\u9664\u6cd5\u3068\u3042\u308b\u3068\u304a\u308a\u4e92\u3044\u306b\u5272\u308a\u7b97\u3092\u884c\u3063\u3066\u89e3\u3092\u5c0e\u304d\u51fa\u3059\u65b9\u6cd5\u3067\u3059\u3002<\/p>\n<p>\u7c21\u5358\u306b\u8aac\u660e\u3059\u308b\u3068\u81ea\u7136\u6570 r1 \u3068 r 2 ( r1 &gt;= r2 ) \u306e\u6700\u5927\u516c\u7d04\u6570\u3092\u6c42\u3081\u308b\u3068\u304d ( \u6ce8\u610f : r \u306e\u5f8c\u306e\u6570\u5b57\u3068 n \u306f\u5c0f\u3055\u3044\u6570\u5b57\u3060\u3068\u601d\u3063\u3066\u304f\u3060\u3055\u3044\u3002)<\/p>\n<p>r1 \/ r2 \u306e\u4f59\u308a r3 \u3092\u6c42\u3081\u308b\u3002<\/p>\n<p>\u6b21\u306b r2 \/ r3 \u306e\u4f59\u308a r4 \u3092\u30fb\u30fb\u30fb<\/p>\n<p>\u3053\u308c\u3092 rn \u304c 0 \u306b\u306a\u308b\u307e\u3067\u7e70\u308a\u8fd4\u3059\u3002<\/p>\n<p>\u3053\u306e\u6642\u3001 r(n-1) \u304c\u6700\u5927\u516c\u7d04\u6570\u3068\u306a\u308b\u3002<\/p>\n<p>\u5b9f\u306b\u30b7\u30f3\u30d7\u30eb\u3067\u3059\u3002<\/p>\n<p>\u6570\u5b66\u7684\u8a3c\u660e\u306f\u3053\u3053\u3067\u306f\u5272\u611b\u3055\u305b\u3066\u3044\u305f\u3060\u304d\u307e\u3059\u3002<\/p>\n<p>\u3053\u308c\u3092 Java \u30d7\u30ed\u30b0\u30e9\u30e0\u306b\u3059\u308b\u306b\u306f\u518d\u5e30\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u4f7f\u3048\u3070\u7c21\u5358\u306b\u3067\u304d\u305d\u3046\u3067\u3059\u306d\u3002<\/p>\n<p>\u3055\u3063\u305d\u304f\u4f5c\u3063\u3066\u307f\u307e\u3057\u3087\u3046\u3002<\/p>\n<style type=\"text\/css\">\n<!--\ntable {color: #000000; background-color: #e9e8e2; font-family: \u3086\u305f\u307d\u3093\uff08\u30b3\u30fc\u30c7\u30a3\u30f3\u30b0\uff09}\n-->\n<\/style>\n<table width=\"100%\">\n<tbody>\n<tr>\n<td align=\"left\"><font size=\"4\">euclidean_algorithm.Euclidean_Algorithm.java<\/font><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<pre>\r\npackage euclidean_algorithm;\r\n\r\n\/**\r\n *\r\n * @author Yucchi\r\n *\/\r\npublic class Euclidean_Algorithm {\r\n\r\n    public static void main(String[] args) {\r\n        if (args.length != 2) {\r\n            System.err.println(\"\u3048\u3089\u30fc (\u309c\u00b4\u0414\uff40\u309c) \u81ea\u7136\u6570\u3092\u4e8c\u3064\u5165\u529b\u3057\u3066\u306d\u3002\");\r\n            System.exit(0);\r\n        }\r\n\r\n        int x = java.lang.Integer.parseInt(args[0]);\r\n        int y = java.lang.Integer.parseInt(args[1]);\r\n\r\n        if (x < 0 || y < 0) {\r\n            System.err.println(\"\u3048\u3089\u30fc (\u309c\u00b4\u0414\uff40\u309c) \u81ea\u7136\u6570\u3092\u4e8c\u3064\u5165\u529b\u3057\u3066\u306d\u3002\");\r\n            System.exit(0);\r\n        }\r\n        \r\n        if (x < y) {\r\n            y ^= x;\r\n            x ^= y;\r\n            y ^= x;\r\n        }\r\n        \r\n        System.out.println(args[0] + \" \u3068 \" + args[1] + \" \u306e\u6700\u5927\u516c\u7d04\u6570\u306f \" + gcd(x, y) + \" \u3060\u3088\u306d\u3002\");\r\n        \r\n    }\r\n\r\n    private static int gcd(int x, int y) {\r\n        return y == 0 ? x : gcd(y, x % y);\r\n    }\r\n}\r\n\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p>\u975e\u5e38\u306b\u30b7\u30f3\u30d7\u30eb\u3067\u89e3\u308a\u3084\u3059\u3044\u3067\u3059\u306d\u3002<\/p>\n<p>\u305b\u3063\u304b\u304f\u3060\u304b\u3089\u30c7\u30d0\u30c3\u30b0\u5b9f\u884c\u3055\u305b\u3066\u30d7\u30eb\u30b0\u30e9\u30e0\u306e\u6d41\u308c\u3092\u78ba\u8a8d\u3057\u3066\u307f\u3088\u3046\u3002<\/p>\n<p>\u5909\u6570 x , y \u306e\u5024\u306b\u6ce8\u76ee\u3067\u3059\u3002<\/p>\n<p><video width=\"900\" height=\"507\" controls><source src=\"http:\/\/yucchi.jp\/movie\/euclidean_algorithm\/euclidean_algorithm_low.mp4\" type=\"video\/mp4\">\u3042\u306a\u305f\u304c\u3054\u5229\u7528\u306e\u30d6\u30e9\u30a6\u30b6\u3067\u306f\u518d\u751f\u3067\u304d\u307e\u305b\u3093\u3067\u3057\u305f\u3002<\/video><\/p>\n<p>main() \u30e1\u30bd\u30c3\u30c9\u306e\u5f15\u6570\u4e8c\u3064\u3092\u6574\u6570\u3068\u3057\u3001\u5927\u304d\u3055\u3092\u6bd4\u8f03\u3057\u8a08\u7b97\u51e6\u7406\u306e\u305f\u3081\u5fc5\u8981\u306b\u5fdc\u3058\u3066\u5024\u3092\u5165\u308c\u66ff\u3048\u3001<\/p>\n<p>\u518d\u5e30\u30e1\u30bd\u30c3\u30c9\u3067\u7b54\u3048\u304c\u51fa\u308b\u307e\u3067(\u518d\u5e30\u306e\u30eb\u30fc\u30d7\u304b\u3089\u629c\u3051\u308b\u6761\u4ef6\u306b\u306a\u308b\u307e\u3067\uff09\u3072\u305f\u3059\u3089\u3050\u308b\u3050\u308b\u56de\u308b\u3063\u3066\u304b\u3093\u3058\u3002<\/p>\n<p><a href=\"http:\/\/yucchi.jp\/blog\/wp-content\/uploads\/2013\/01\/euclidean_algorithm.png\" target=\"_blank\"><img loading=\"lazy\" decoding=\"async\" title=\"euclidean_algorithm\" style=\"border-left-width: 0px; border-right-width: 0px; background-image: none; border-bottom-width: 0px; padding-top: 0px; padding-left: 0px; display: inline; padding-right: 0px; border-top-width: 0px\" border=\"0\" alt=\"euclidean_algorithm\" src=\"http:\/\/yucchi.jp\/blog\/wp-content\/uploads\/2013\/01\/euclidean_algorithm_thumb.png\" width=\"640\" height=\"343\"><\/a><\/p>\n<p>\u30e6\u30fc\u30af\u30ea\u30c3\u30c9\u306e\u4e92\u9664\u6cd5\u3063\u3066\u30b7\u30f3\u30d7\u30eb\u3060\u3051\u3069\u826f\u304f\u8003\u3048\u3089\u308c\u305f\u7d20\u6674\u3089\u3057\u3044\u3082\u306e\u3067\u3059\u306d\u3002<\/p>\n<p>\u6700\u5f8c\u306b\u3059\u3067\u306b\u304a\u6c17\u4ed8\u304d\u306e\u65b9\u3082\u3044\u308b\u3068\u601d\u3046\u306e\u3067\u3059\u304c\u4e0a\u8a18\u30d7\u30ed\u30b0\u30e9\u30e0\u306f\u3061\u3087\u3063\u3068\u624b\u629c\u304d\u306e\u90e8\u5206\u304c\u3042\u308a\u307e\u3059\u3002<\/p>\n<p>\u76ee\u7684\u304c\u30e6\u30fc\u30af\u30ea\u30c3\u30c9\u306e\u4e92\u9664\u6cd5\u3092\u8a66\u3057\u3066\u307f\u308b\u3068\u3044\u3046\u3053\u3068\u306a\u306e\u3067\u3054\u5bb9\u8d66\u306e\u307b\u3069\u3092(^_^;<\/p>\n<p>\u3061\u306a\u307f\u306b java.lang.NumberFormatException \u304c\u30fb\u30fb\u30fb\u30fb\u30fb\u30fb\u3067\u3059\u3002\uff08\u672c\u5f53\u306f\u5fd8\u308c\u3066\u3044\u305f\u3053\u3068\u306f\u5185\u7dd2\u3067\u3059\uff09<\/p>\n<p><a href=\"http:\/\/yucchi.jp\/blog\/wp-content\/uploads\/2013\/01\/a_001.jpg\" target=\"_blank\"><img loading=\"lazy\" decoding=\"async\" title=\"a_001\" style=\"border-left-width: 0px; border-right-width: 0px; background-image: none; border-bottom-width: 0px; padding-top: 0px; padding-left: 0px; display: inline; padding-right: 0px; border-top-width: 0px\" border=\"0\" alt=\"a_001\" src=\"http:\/\/yucchi.jp\/blog\/wp-content\/uploads\/2013\/01\/a_001_thumb.jpg\" width=\"859\" height=\"595\"><\/a><\/p>\n<div id=\"scid:0767317B-992E-4b12-91E0-4F059A8CECA8:b1990ed2-9d00-419f-ac3f-0932634b1ac9\" class=\"wlWriterEditableSmartContent\" style=\"float: none; padding-bottom: 0px; padding-top: 0px; padding-left: 0px; margin: 0px; display: inline; padding-right: 0px\">Hatena \u30bf\u30b0: <a href=\"http:\/\/b.hatena.ne.jp\/t\/Java\" rel=\"tag\">Java<\/a><\/div>\n<div class='wp_social_bookmarking_light'>\n            <div class=\"wsbl_hatena\"><a href='\/\/b.hatena.ne.jp\/add?mode=confirm&url=http%3A%2F%2Fyucchi.jp%2Fblog%2F%3Fp%3D550&title=%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95%20Euclidean%20Algorithm' title='\u3053\u306e\u30a8\u30f3\u30c8\u30ea\u30fc\u3092\u306f\u3066\u306a\u30d6\u30c3\u30af\u30de\u30fc\u30af\u306b\u8ffd\u52a0' rel=nofollow class='wp_social_bookmarking_light_a' target=_blank><img src='http:\/\/yucchi.jp\/blog\/wp-content\/plugins\/wp-social-bookmarking-light\/public\/images\/hatena.gif' alt='\u3053\u306e\u30a8\u30f3\u30c8\u30ea\u30fc\u3092\u306f\u3066\u306a\u30d6\u30c3\u30af\u30de\u30fc\u30af\u306b\u8ffd\u52a0' title='\u3053\u306e\u30a8\u30f3\u30c8\u30ea\u30fc\u3092\u306f\u3066\u306a\u30d6\u30c3\u30af\u30de\u30fc\u30af\u306b\u8ffd\u52a0' width='16' height='12' class='wp_social_bookmarking_light_img' \/><\/a><\/div>\n            <div class=\"wsbl_facebook\"><a href='http:\/\/www.facebook.com\/share.php?u=http%3A%2F%2Fyucchi.jp%2Fblog%2F%3Fp%3D550&t=%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95%20Euclidean%20Algorithm' title='Facebook \u306b\u30b7\u30a7\u30a2' rel=nofollow class='wp_social_bookmarking_light_a' target=_blank><img src='http:\/\/yucchi.jp\/blog\/wp-content\/plugins\/wp-social-bookmarking-light\/public\/images\/facebook.png' alt='Facebook \u306b\u30b7\u30a7\u30a2' title='Facebook \u306b\u30b7\u30a7\u30a2' width='16' height='16' class='wp_social_bookmarking_light_img' \/><\/a><\/div>\n            <div class=\"wsbl_google_plus_one\"><g:plusone size=\"medium\" annotation=\"none\" href=\"http:\/\/yucchi.jp\/blog\/?p=550\" ><\/g:plusone><\/div>\n            <div class=\"wsbl_twitter\"><a href=\"https:\/\/twitter.com\/share\" class=\"twitter-share-button\" data-url=\"http:\/\/yucchi.jp\/blog\/?p=550\" data-text=\"\u30e6\u30fc\u30af\u30ea\u30c3\u30c9\u306e\u4e92\u9664\u6cd5 Euclidean Algorithm\" data-lang=\"ja\">Tweet<\/a><\/div>\n    <\/div>\n<br class='wp_social_bookmarking_light_clear' \/>\n","protected":false},"excerpt":{"rendered":"<p>Java \u3067\u30e6\u30fc\u30af\u30ea\u30c3\u30c9\u306e\u4e92\u9664\u6cd5\u3000Euclidean Algorithm \u3092\u30d7\u30ed\u30b0\u30e9\u30df\u30f3\u30b0\u3057\u3066\u307f\u307e\u3057\u305f\u3002 \u518d\u5e30\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u4f7f\u3063\u3066\u307e\u3059\u3002 \u518d\u5e30\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306b\u3064\u3044\u3066\u306f\u3053\u3061\u3089\u3067\u7c21\u5358\u306a\u899a\u3048\u66f8\u304d\u3092\u6b8b\u3057\u3066\u3042\u308a\u307e\u3059\u3002 \u518d\u5e30\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3000\u305d\u306e\uff11 \u518d\u5e30\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3000\u305d\u306e\uff12 \u30e6\u30fc\u30af\u30ea\u30c3\u30c9\u306e\u4e92\u9664\u6cd5\u3068\u306f\u3044\u3063\u305f\u3044\u3069\u3093\u306a\u4ed5\u7d44\u307f\u306a\u306e\u304b\u8abf\u3079\u3066\u307f\u307e\u3057\u305f\u3002 \u3042\u308b\u4e8c\u3064\u306e\u81ea\u7136\u6570\u306e\u6700\u5927\u516c\u7d04\u6570\u3092\u6c42\u3081\u308b\u306e\u306b\u975e\u5e38\u306b\u512a\u308c\u305f\u65b9\u6cd5\u3089\u3057\u3044\u3067\u3059\u3002 \u540d\u524d\u306b\u4e92\u9664\u6cd5\u3068\u3042\u308b\u3068\u304a\u308a\u4e92\u3044\u306b\u5272\u308a\u7b97\u3092\u884c\u3063\u3066\u89e3\u3092\u5c0e\u304d\u51fa\u3059\u65b9\u6cd5\u3067\u3059\u3002 \u7c21\u5358\u306b\u8aac\u660e\u3059\u308b\u3068\u81ea\u7136\u6570 r1 \u3068 r 2 ( r1 &gt;= r2 ) \u306e\u6700\u5927\u516c\u7d04\u6570\u3092\u6c42\u3081\u308b\u3068\u304d ( \u6ce8\u610f : r \u306e\u5f8c\u306e\u6570\u5b57\u3068 n \u2026<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[17],"class_list":["post-550","post","type-post","status-publish","format-standard","hentry","category-java","tag-java"],"_links":{"self":[{"href":"http:\/\/yucchi.jp\/blog\/index.php?rest_route=\/wp\/v2\/posts\/550","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/yucchi.jp\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yucchi.jp\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yucchi.jp\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/yucchi.jp\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=550"}],"version-history":[{"count":4,"href":"http:\/\/yucchi.jp\/blog\/index.php?rest_route=\/wp\/v2\/posts\/550\/revisions"}],"predecessor-version":[{"id":824,"href":"http:\/\/yucchi.jp\/blog\/index.php?rest_route=\/wp\/v2\/posts\/550\/revisions\/824"}],"wp:attachment":[{"href":"http:\/\/yucchi.jp\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=550"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yucchi.jp\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=550"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yucchi.jp\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=550"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}