Алгоритм Эвклида!

Тема в разделе "WASM.A&O", создана пользователем EvilsInterrupt, 15 фев 2005.

  1. EvilsInterrupt

    EvilsInterrupt Постигающий азы дзена

    Публикаций:
    0
    Регистрация:
    28 окт 2003
    Сообщения:
    2.428
    Адрес:
    Russia
    Реализовал на си++ этот алгоритм, но возникают проблемы с табуляцией. Т.е при больших числах а и b верхние результаты танциют в таблице.

    Пожалуйста помогите наладить табуляцию, чтобы таблица получалась красивой

    [​IMG] 1956306151__euclide_II.cpp
     
  2. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    EvilsInterrupt

    printf тебе поможет:
    Код (Text):
    1. for(int i=0;i<32;i++)
    2.     printf("2^%2d =% 11lu\n",i,1UL<<i);
     
  3. q_q

    q_q New Member

    Публикаций:
    0
    Регистрация:
    5 окт 2003
    Сообщения:
    1.706
    EvilsInterrupt

    Output Formatting.



    ps какое отношение "Алгоритм Эвклида!" имеет к "помогите наладить табуляцию"?
     
  4. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.754
    =)

    Совсем какая-то фигня на Θоруме :-(


    Код (Text):
    1. // Euclide.js
    2.  
    3. var title = WScript.ScriptName.replace(/.js/i,'');
    4. var IE = new ActiveXObject ('InternetExplorer.Application');
    5. IE.navigate("about:blank");
    6. IE.toolbar = IE.statusbar = 0;
    7. IE.visible = true;
    8.  
    9. while( IE.Busy ){}
    10. var form = IE.Document;
    11.  
    12. form.open;
    13. form.write('<html><head><title>'+title+'</title></head><body><font face=system>');
    14. form.write('<form>Enter numbers');
    15. form.write('<p>a: <input type="text" size="10" maxlength="12" name="a]');
    16. form.write(' &nbspb: <input type="text" size="10" maxlength="12" name="b]  ');
    17. form.write('<button onclick="document.Ok=true; document.a=a.value; document.b=b.value]');
    18. form.write('Ok</button></form>');
    19.  
    20. try
    21. {    
    22.     while( ! form.Ok ){}
    23.  
    24.     form.write('<table border=1><caption>results</caption>');
    25.     form.write('<tr><th>iteration<th>a<th>b<th>r');
    26.  
    27.     var r, i = 0;    var a = form.a;    var b = form.b;
    28.  
    29.     do
    30.     {
    31.         r = a % b;
    32.         form.write('<tr><td>'+ ++i +'<th>'+ a +'<th>'+ b +'<td>'+ r);
    33.         a = b;    b = r;
    34.     }
    35.     while( r > 1 );
    36.  
    37.     form.write('</table><br>r(end) = '+ r);
    38.     form.write('<br>gcd(end) = '+ (r ? r : a) );
    39.  
    40.     form.write('<br><br><button onclick="document.Close=true]Close</button></body></html>');
    41.  
    42.     try
    43.     {
    44.         while( ! form.Close ){}
    45.         IE.Quit();
    46.     }
    47.     catch(e){}
    48. }
    49. catch(e){}
    50.  




    PS парсер &nbsp_ повыкидывал
     
  5. EvilsInterrupt

    EvilsInterrupt Постигающий азы дзена

    Публикаций:
    0
    Регистрация:
    28 окт 2003
    Сообщения:
    2.428
    Адрес:
    Russia
    В рассширенной версии этого алгоритма есть возможность найти такие числа u,v при которых выполнится равенство:



    av+bu=d, где d - есть НОД



    Как правило по началу необходимо предположить что u-1 = 1, u0 = 0, v0 = 0 v-1 = 1 если смотреть это по Коутинхо.



    Чем это вызвано? Почему не наоборот v0,u0 =1,u-1,v-1=0 ?
     
  6. EvilsInterrupt

    EvilsInterrupt Постигающий азы дзена

    Публикаций:
    0
    Регистрация:
    28 окт 2003
    Сообщения:
    2.428
    Адрес:
    Russia
    Спасибо помолчали, буду помирать никто и руки не подаст. Ладно понял все тонкости этого расширения, а такбы мучился!



    Если кто решил изучать теорию чисел, то настоятельно советую Коутинхо, т.к. там даже мат.неподготовленный имеет все шансы познать хотя бы азы!



    Володя:

    Если эта книга фри, а линк я те давал, то это книгу имеет смысл выложить на сайте, она лучше Сизова :), дает понять теорию чисел, а я бы сказал глубже. К примеру сравни как объяснено нахождение a*u + b*v = gcd(a,d), u,v = ? И увидишь ощутимую разницу.
     
  7. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    Блин, Сизый вообще не объясняет твой расширенный алгоритм, куда ты так упрямо лезешь. А где ты там увидел глубокую теорию - я не очень понимаю. Да, конечно, можно приплести нахождение обратного элемента и подвести глубокую базу по кольцам, но зачем?
     
  8. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    u-1 = 1, u0 = 0, v0 = 0 v-1 = 1



    чего?



    u-1 = 1? т.е. u = 2?

    ты здоров, алгоритмист?
     
  9. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    т.к. там даже мат.неподготовленный имеет все шансы познать хотя бы азы!



    ты, со своими талантами, имеешь все шансы свести с ума любого, кто пытается разобраться в твоей писанине - именно поэтому никто и не пытается ответить.
     
  10. EvilsInterrupt

    EvilsInterrupt Постигающий азы дзена

    Публикаций:
    0
    Регистрация:
    28 окт 2003
    Сообщения:
    2.428
    Адрес:
    Russia
    >"советую Коутинхо" && "она лучше Сизова" && "я бы сказал глубже".



    По моему ты читаешь скоростным методом, ведь привел Автора книги, о ней говорю, а вопросы возникают. Отдохни, устал поди.



    >u-1 = 1? т.е. u = 2?

    ты здоров, алгоритмист?



    я задавал вопрос,почему не так! А не утверждал,видно же
     
  11. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    volodya





    На самом деле имеется в виду:

    u<sub>-1</sub>=1, u<sub>0</sub>=0, v<sub>0</sub>=0, v<sub>-1</sub>=1