Как найти большее число алгоритм

3. Проверьте его работу. 

4. Сохраните проект под именем упражнение_13_1

Перейти к содержанию

// 1-й способ:


var 

    a,b,c,max: integer;

begin

    readln(a,b,c);

    max := a;

    if max < b then max := b;

    if max < c then max := c;

    writeln(max);

end.


// 2-й способ:


var 

    a,b,c: integer;

begin

    readln(a,b,c);

    if a > b then 

        if a > c then writeln(a)

        else writeln(c)

    else 

        if b > c then writeln(b)

        else writeln(c);

end.

// 1-й вариант:


#include 

 
main() {

    int a,b,c,m;

    scanf("%d%d%d",&a,&b,&c);

    m = a;

    if (m < b) m = b;

    if (m < c) m = c;

    printf("%dn", m);

}



  


                       
  





// 2-й вариант:


#include 

 
main() {

    int a,b,c;

    scanf("%d%d%d",&a,&b,&c);

 
    if (a > b) 

        if (a > c) printf("%dn", a);

        else printf("%dn", c);

    else

        if (b > c) printf("%dn", b);

        else printf("%dn", c);

}

# 1-й вариант:


a = int(input())

b = int(input())

c = int(input())

 
m = a

if m < b:

    m = b

if m < c:

    m = c



  


                       
  




 
print(m)


# 2-й вариант:


a = int(input())

b = int(input())

c = int(input())

 
if a > b:

    if a > c:

        print(a)

    else:

        print(c)

else:

    if b > c:

        print(b)

    else:

        print(c)

| 1-й вариант:


алг максимум из трех

нач

  цел a, b, c, m

  ввод a, b, c

  m := a

  если b > m то m := b все

  если c > m то m := c все

  вывод m

кон


| 2-й вариант:


алг максимум из трех

нач

  цел a, b, c

  ввод a, b, c

  если a > b то

    если a > c то

      вывод a

     иначе

      вывод c

    все

   иначе

    если b > c то

      вывод b

     иначе 

      вывод c

    все

  все

кон



  


                       
  

# 1-й вариант:


input a

input b

input c

max = a

if max < b then max = b

if max < c then max = c

print max


# 2-й вариант:


input a

input b

input c

if a > b then 

	if a > c then 

		print a

	else 

		print c

	endif

else

	if b > c then 

		print b

	else 

		print c

	endif

endif

Самый распространенный вариант реализации функции max — проверка знака выражения a - b. В этом случае мы не можем использовать оператор сравнения, но можем использовать умножение.

Примечание Смысл задачи не в том, чтобы скрыть сравнение или условие в какую-нибудь стандартную функцию типа abs() или стандартный оператор типа целочисленного деления, а в том, чтобы всё это сделать вообще без инструкций ветвления на уровне процессора.

Обозначим знак выражения a - b как k. Если a - b >= 0, то k = 1, иначе k = 0. Пусть q будет инвертированным значением k.

Код будет иметь вид:

/* Отражаем 1 в 0 и 0 в 1 */
int flip(int bit) {
	return 1^bit;
}

/* Возвращаем 1, если число положительное, и 0, если отрицательное*/
int sign(int a) {
	return flip((a >> (sizeof(int) * CHAR_BIT - 1)))) & 0x1);
}

int getMaxNaive(int a, int b) {
	int k = sign(a - b);
	int q = flip(k);
	return a * k + b * q;
}

Это почти работоспособный код (можете проверить). Проблемы начинаются при переполнении. Предположим, что a = INT_MAX - 2 и b = -15. В этом случае a - b перестанет помещаться в INT_MAX и вызовет переполнение (значение станет отрицательным).

Можно использовать тот же подход, но придумать другую реализацию. Нам нужно, чтобы выполнялось условие k = 1, когда a > b. Для этого придется использовать более сложную логику.

Когда возникает переполнение a - b? Только тогда, когда a положительное число, а b отрицательное (или наоборот). Трудно обнаружить факт переполнения, но мы в состоянии понять, что a и b имеют разные знаки. Если у а и b разные знаки, то пусть k = sign(a).

Логика будет следующей:

1. если у a и b разные знаки:
// если a > 0, то b < 0 и k = 1.
// если a < 0, то b > 0 и k = 0.
// так или иначе, k = sign(a)
2. пусть k = sign(a)
3. иначе пусть k = sign(a - b) // переполнение невозможно

Приведенный далее код реализует этот алгоритм, используя умножение вместо операторов сравнения (проверить):

int getMax(int a, int b) {
	int c = a - b;
	
	int sa = sign(a); // если a >= 0, то 1, иначе 0
	int sb = sign(b); // если a >= 1, то 1, иначе 0
	int sc = sign(c); // зависит от переполнения a - b
	
	/* Цель: найти k, которое = 1, если а > b, и 0, если a < b.
	 * если a = b, k не имеет значения */

	// Если у а и b равные знаки, то k = sign(a)
	int use_sign_of_a = sa ^ sb;
	
	// Если у a и b одинаковый знак, то k = sign(a - b)
	int use_sign_of_c = flip(sa ^ sb);
	
	int k = use_sign_of_a * sa + use_sign_of_c * sc;
	int q = flip(k); // отражение k

	return a * k + b * q;
}

Отметим, что для большей наглядности мы разделяем код на методы и вводим переменные. Это не самый компактный или эффективный способ написания кода, но так мы делаем код понятнее.

_{Разбор взят из книги Гейл Л. Макдауэлл «Cracking the Coding Interview» (есть в переводе).}