Программа для нахождения......

@Planet · Регистрация: 07.11.2009

Нужна программа на языке Cи для нахождения наибольшего общего делителя для двух натуральных числел, никак не могу сообразить как это сделать, помогите ,пожалуйста

@SONNY · 07.11.2009, 02:34

http://ru.wikipedia.org/wiki/%... 0%9E%D0%94

@Planet · 07.11.2009, 02:35 **[ТС]**

Я это читал, как это сделать , весь алгаритм понял, НО как записать это в программном коде?
я не понимаю, помогите,пожалуйста, я совсем уже замучался, а то что ниже, мне не понятно, мы еще этого не проходили( я про shift и т.д)

@Varlock · 07.11.2009, 06:05

там же прямо и написано

реализация на С

давай подробней, что именно тебе непонятно (коментировать весь код мне лень

)

shift - это переменная типа инт

Код

int shift;

вот они в самом начале её объявили

ничего сложного, чего можно было бы "не проходить" или не найти мигом в инете я там не увидел...
ифы, циклы, стандартные операции... собственно того, чего могло быть не рассказано на первых двух лекциях, или не написано в любой книге по С, я там вижу только >>= и <<

на что та же википедия нам сразу может дать ответ

например >>= - относится к операторам присваивания

З.Ы. собственно помнить только стоит чем логические операции от побитовых отличаются, и чем
++shift будет отличаться от shift++

@HIMen · 07.11.2009, 10:25

C

#include <stdio.h>
unsigned int gcd(unsigned int u, unsigned int v)
{
    int shift;
    /* GCD(0,x) := x */
    if (u == 0 || v == 0)
    {
        return u | v;
    }
    /* Let shift := lg K, where K is the greatest power of 2
    dividing both u and v. */
    for (shift = 0; ((u | v) & 1) == 0; ++shift)
    {
        u >>= 1;
        v >>= 1;
    }
    while ((u & 1) == 0)
    {
        u >>= 1;
    }
    /* From here on, u is always odd. */
    do
    {
        while ((v & 1) == 0)  /* Loop X */
            v >>= 1;
 
        /* Now u and v are both odd, so diff(u, v) is even.
        Let u = min(u, v), v = diff(u, v)/2. */
        if (u < v)
        {
            v -= u;
        }
        else
        {
            unsigned int diff = u - v;
            u = v;
            v = diff;
        }
        v >>= 1;
    } while (v != 0);
    return u << shift;
}
int main()
{
    unsigned int u, v;
    printf("Vvedite pervoe 4islo: ");
    scanf("%u",&u); 
    printf("Vvedite vtoroe 4islo: ");
    scanf("%u",&v); 
    printf("NOD: %u",gcd(u,v));
    return 0;
}

@Planet · 07.11.2009, 19:34 **[ТС]**

Просто мне надо без использования Shift ) Unsigned и только в конце 1 Return 0;
а не в середине где то еще..
с помощью цикла for или while (do...while).
Эта прога работает, но препод меня не поймет)

@SONNY · 07.11.2009, 19:38

C++

int NOD(int a,int b)
 {
    while(a!=0 && b!=0)
    {
       if(a>=b) a=a%b;
           else b=b%a;
    }
 return a+b; // Одно - ноль
 }

valeriikozlov · 07.11.2009, 22:00

https://www.cyberforum.ru/cpp-... 61972.html

@Planet 0 / 0 / 0 Регистрация: 07.11.2009 Сообщений: 52
		1
	Программа для нахождения...... 07.11.2009, 02:28. Просмотров 841. Ответов 7 Метки нет (Все метки) Нужна программа на языке Cи для нахождения наибольшего общего делителя для двух натуральных числел, никак не могу сообразить как это сделать, помогите ,пожалуйста 0

@SONNY 8 / 8 / 5 Регистрация: 30.05.2009 Сообщений: 47
	07.11.2009, 02:34	2
	http://ru.wikipedia.org/wiki/%... 0%9E%D0%94 0

@Planet 0 / 0 / 0 Регистрация: 07.11.2009 Сообщений: 52
	07.11.2009, 02:35 [ТС]	3
	Я это читал, как это сделать , весь алгаритм понял, НО как записать это в программном коде? я не понимаю, помогите,пожалуйста, я совсем уже замучался, а то что ниже, мне не понятно, мы еще этого не проходили( я про shift и т.д) 0

@Varlock 365 / 68 / 2 Регистрация: 25.09.2008 Сообщений: 401
	07.11.2009, 06:05	4
	там же прямо и написано реализация на С давай подробней, что именно тебе непонятно (коментировать весь код мне лень ) shift - это переменная типа инт Код int shift; вот они в самом начале её объявили ничего сложного, чего можно было бы "не проходить" или не найти мигом в инете я там не увидел... ифы, циклы, стандартные операции... собственно того, чего могло быть не рассказано на первых двух лекциях, или не написано в любой книге по С, я там вижу только >>= и << на что та же википедия нам сразу может дать ответ например >>= - относится к операторам присваивания З.Ы. собственно помнить только стоит чем логические операции от побитовых отличаются, и чем ++shift будет отличаться от shift++ 0

@Planet 0 / 0 / 0 Регистрация: 07.11.2009 Сообщений: 52
	07.11.2009, 19:34 [ТС]	6
	Просто мне надо без использования Shift ) Unsigned и только в конце 1 Return 0; а не в середине где то еще.. с помощью цикла for или while (do...while). Эта прога работает, но препод меня не поймет) 0

valeriikozlov 4709 / 2534 / 753 Регистрация: 18.08.2009 Сообщений: 4,550
	07.11.2009, 22:00	8
	https://www.cyberforum.ru/cpp-... 61972.html 0

Опции темы