Школьная задачка
18 июля 2006
Помнится в школе, на уроке информатики, мне не хотелось особо показывать что я разбираюсь в компьютерах, вечно задавал глупые вопросы, отвечал с ошибками и т.д
И вот как-то был урок на тему «условного ветвления». Проходили тогда какой-то Бейсик, но это не суть важно. Так вот на дом было следующее задание: «Написать программу, которая спрашивает у пользователя значение X и Y. Далее программа должна вывести на экран какое значение больше, т.е. X или Y».
Я, уже не знаю зачем, сказал «что-то я не разобрался с условиями, «ифами» и пр. Можно я сделаю это без условий?» Учитель, конечно, улыбнулась моей наивности и сказала, что если я так сделаю, то 5 обеспечена.
Зачем так сказал не знаю, но следующие пару дней я ходил и думал как же на этом бейсике сделать такую программу и при этом не использовать никакого условного перехода… И ведь придумал!
Я написал прогу, которая спрашивает у пользователя эти две переменные и выводит на экран название наибольшей переменной. При этом в программе не было не единого условия (даже как-то завуалированного и типа того). Учитель так и не смогла понять, как «это» работает, но факт, программа выдавала правильные ответы! 
Я этой зимой уже вспоминал об этой шутке, товарищ Мельников ее даже решил. Правда можно было бы чуток прооптимизировать, и подход немного другой, но, по сути, было похоже на то как я писал.
Так вот, теперь хотелось бы задать эту же задачку моим уважаемым читателям Если у кого появится мысль как это реализовать, то пришлите вариант решения на igor@artamonov.ru. В комментарии писать ответ не стоит, я потом опубликую интересные решения. Язык программирования не особо важен, если он из алгоритмических. Так как компилировать я не собираюсь, то, для понятности, лучше написать на чем-то похожем на паскаль или вообще по-русски Варианты принимаются до 5 августа 2006г. Ну что, кому хочется показать себя?
Мне скорее интересно не то чтобы нашли именно мое решение, а вообще какие тут вообще решения такой задачи возможны, помоему их будет порядочно. И еще, хотелось бы проверить действительно это простая задача или нет, потому что сейчас, зная решение, кажется что это элементарно.
Update: имелось ввиду вывести не само наибольшее значение, а имя наибольшей переменной.
Т.е. диалог примерно такой:
Введите A:
1
Введите B:
3
Наибольшее значение в переменной: B
июля 18, 2006 в 14:23
Школьная, у меня без минусов правда
(($a+$b)-(($a+$b)-abs($a-$b))/2);
июля 19, 2006 в 07:10
array (x,y)[(int) ((x%y) && (x%y)) ]
июля 19, 2006 в 07:11
array (x,y)[(int) ((y%x) && (y%x)) ] – ошибся
июля 19, 2006 в 07:38
Именно if-ы нельзя использовать, или вообще операцию сравнения в любом виде и различные условные конструкции?
Если можно использовать condition ? trueValue : falseValue, или условную конструкцию в while(), то все вообще просто. А если нет, то.. счас пришлю соображения, интересную задачку загадал.
июля 19, 2006 в 10:58
Не, это нельзя пользовать
июля 19, 2006 в 16:51
числа могут быть отрицательными?
июля 20, 2006 в 10:44
Ну это почти очевидно тем, кто знаком с функциональным программированием.
: func1()
elif : func2()
else: func3()
# Эквивалентное «накоротко замкнутое» выражение
( and func1()) or ( and func2()) or (func3()> (подробности смотри по http://www.iso.ru/journal/articles/75.html)
В Java это, как и многое другое, не поддерживается явно, поэтому поиграем битами:
/*
* Created by Ulanov D.P. at Jul 20, 2006 12:25:39 PM
*
* $LastChangedBy$
* $LastChangedDate$
* $LastChangedRevision$
*/
package ru.festo;
import junit.framework.TestCase;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
/**
* ?????????? ????????? ??? ????????? ???? ????????????? ????? ? ?????? ???????? ?? ??? ??? ????????????? ??????????? ?????????.
*
* ????: ??? ????????????? ?????
* ?????: ???????? ???????? ?????
*
* ???????? ??????: http://www.artamonov.ru/2006/07/18/shkolnaya-zadachka/
*/
public class NumberComparator extends TestCase {
/**
* @return 1 ???? a > b ????? 0
*/
private static int isGreater(int a, int b) {
return ((((a – b) & 0×80000000) >> 31) & 1) ^ 1;
}
public static int greater(int a, int b) {
//return (a > b) && a || b; // ?? ?????????????? ? Java
return a * isGreater(a, b) + b * isGreater(b, a);
}
public void testISGreater() {
assertEquals(0, NumberComparator.isGreater(0, 1));
assertEquals(1, NumberComparator.isGreater(1, 0));
assertEquals(0, NumberComparator.isGreater(1, 2));
assertEquals(1, NumberComparator.isGreater(2, 1));
}
public void testGreater() {
assertEquals(1, NumberComparator.greater(0, 1));
assertEquals(1, NumberComparator.greater(1, 0));
assertEquals(2, NumberComparator.greater(1, 2));
assertEquals(2, NumberComparator.greater(2, 1));
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
System.out.println(«Input A:»);
int a = Integer.decode(in.readLine()).intValue();
System.out.println(«Input B:»);
int b = Integer.decode(in.readLine()).intValue();
System.out.println(«Greater value is: » + greater(a, b));
}
}
июля 20, 2006 в 10:46
Ну это почти очевидно тем, кто знаком с функциональным программированием.
: func1()
elif : func2()
else: func3()
# Эквивалентное «накоротко замкнутое» выражение
( and func1()) or ( and func2()) or (func3()> (подробности смотри по http://www.iso.ru/journal/articles/75.html)
В Java это, как и многое другое, не поддерживается явно, поэтому поиграем битами:
/*
* Created by Ulanov D.P. at Jul 20, 2006 12:25:39 PM
*
* $LastChangedBy$
* $LastChangedDate$
* $LastChangedRevision$
*/
package ru.festo;
import junit.framework.TestCase;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
/**
* Консольная программа для сравнения двух целочисленных чисел и вывода большего из них без использования конструкции ветвления.
*
* Вход: два целочисленных числа
* Выход: значение большего числа
*
* Источник задачи: http://www.artamonov.ru/2006/07/18/shkolnaya-zadachka/
*/
public class NumberComparator extends TestCase {
/**
* @return 1 если a > b иначе 0
*/
private static int isGreater(int a, int b) {
return ((((a – b) & 0×80000000) >> 31) & 1) ^ 1;
}
public static int greater(int a, int b) {
//return (a > b) && a || b; // не поддерживается в Java
return a * isGreater(a, b) + b * isGreater(b, a);
}
public void testISGreater() {
assertEquals(0, NumberComparator.isGreater(0, 1));
assertEquals(1, NumberComparator.isGreater(1, 0));
assertEquals(0, NumberComparator.isGreater(1, 2));
assertEquals(1, NumberComparator.isGreater(2, 1));
}
public void testGreater() {
assertEquals(1, NumberComparator.greater(0, 1));
assertEquals(1, NumberComparator.greater(1, 0));
assertEquals(2, NumberComparator.greater(1, 2));
assertEquals(2, NumberComparator.greater(2, 1));
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
System.out.println(«Input A:»);
int a = Integer.decode(in.readLine()).intValue();
System.out.println(«Input B:»);
int b = Integer.decode(in.readLine()).intValue();
System.out.println(«Greater value is: » + greater(a, b));
}
}
июля 20, 2006 в 11:16
Update:
/*
* Created by Ulanov D.P. at Jul 20, 2006 12:25:39 PM
*
* $LastChangedBy$
* $LastChangedDate$
* $LastChangedRevision$
*/
package ru.festo;
import junit.framework.TestCase;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* Консольная программа для сравнения двух целочисленных чисел и вывода большего из них без использования конструкции ветвления.
*
* Вход: два целочисленных числа
* Выход: значение большего числа
*
* Источник задачи: http://www.artamonov.ru/2006/07/18/shkolnaya-zadachka/
*/
public class NumberComparator extends TestCase {
private static boolean func(String inString, StringBuffer outString) {
outString.append(inString);
return true;
}
public static String greater(int a1, String s1, int a2, String s2) {
StringBuffer buffer = new StringBuffer();
boolean flag = (a1 > a2) && func(s1, buffer) || func(s2, buffer);
return buffer.toString();
}
public void testGreater() {
assertEquals(«b», NumberComparator.greater(0, «a», 1, «b»));
assertEquals(«a», NumberComparator.greater(1, «a», 0, «b»));
assertEquals(«b», NumberComparator.greater(1, «a», 2, «b»));
assertEquals(«a», NumberComparator.greater(2, «a», 1, «b»));
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
System.out.println(«Input A:»);
int a = Integer.decode(in.readLine()).intValue();
System.out.println(«Input B:»);
int b = Integer.decode(in.readLine()).intValue();
System.out.println(«Greater value is: » + greater(a, «A», b, «B»));
}
}
июля 20, 2006 в 12:19
Глеб, ну это как тебе удобно, главное идея.
В моем решении тоже был косяк с тем что не все числа воспринимала.
ЗЫЖ уже прислали 4 разных варианта решения
июля 24, 2006 в 11:40
А можно пользоваться sign?
Типа посчитать int id = (sign(a-b)+1)
А потом из массива выдать нужную букву?
res[0]=»B»
res[1]=»одинаковые»
res[2]=»A»
июля 24, 2006 в 20:38
Igor. Найти значение это понятно! Но имя переменной- это просто именованная область памяти. Извините за нескромный вопрос: откуда комп узнает как я обозвал переменную?
Я уже не говорю про С++, в котором можно поменять значение переменной, не присваивая его этой переменной! Вы уверены, что у этой задачи есть решение? Упростим задачу!!! Выведите переменные так, как я их обозвал в программе?
июля 24, 2006 в 20:50
Под названием переменных я имел ввиду то, как мы ее показываем пользователю, т.е. все эти «Введите X» и «Введите Y». А как внутри программы именовать это не важно.
июля 26, 2006 в 07:18
Так можно?
public char maxVar(int a, int b) {
char[] names = new char[a + b];
Arrays.fill(names, 0, a, ‘a’);
Arrays.fill(names, a, a + b, ‘b’);
return names[(a + b) >> 1];
}
августа 1, 2006 в 15:18
Я сейчас себе мозг сломаю
Тут какая-то математическмя хитрость?
августа 1, 2006 в 15:29
Ага, у меня была математическая хитрость. Но, судя по предлагаемым решениям, вариантов хитрости может быть очень много. Сам в шоке
августа 3, 2006 в 14:27
Тем не менее, эту задачку нам когда-то предлагали в политехе(Волгоград) на коллоквиуме =)
августа 4, 2006 в 07:35
Есть! Я решил! Отправил свое решение на почту. Когда будут опубликованы все решения?
августа 4, 2006 в 08:02
Сегодня до вечера еще жду всех решений, и завтра выкладываю все способы решения.
августа 20, 2006 в 00:25
жду недождусь.. как на бейсике воплотить такое мне непонятно
сентября 8, 2006 в 10:54
Ну, когда же будут варианты реализации?
сентября 12, 2006 в 14:20
Написал на Java без использования библиотечных функций и каких-либо конструкций (if-then-else, for, while). Когда уже решения будут?
сентября 22, 2006 в 03:51
Написал в одну строчку на python. Жду решений.
сентября 28, 2006 в 09:21
Где же решение?
октября 10, 2006 в 16:42
я думаю что-нибудь в этом роде поможет
max(x, y) = (x + y + abs(x – y)) / 2
Мне тут более интересную задачку задали. написать на джаве прогу которая просит ввести число N и потом печатает числа от 1 до N не используя циклов, условных операторов и перехват эксепшенов.
ноября 27, 2006 в 13:50
не смог написать без оператора сдвига. Идея такая: если разделить A/B то получится либо 0 (А меньше Б) либо что-то больше 1. Соответсвенно сдвигать массив или строку на это число. Но сдвиг по сути тоже условие.
В общем, очень хотел бы посмотреть на решение.
декабря 13, 2006 в 12:52
Не понял, а куда делся пост сегодняшний с решением?
декабря 14, 2006 в 11:00
ага в rss кусочек остался
—————–
Решение задачки было на самом деле простым, если присмотрется к условию Суть ведь не в том чтобы определить кто из них больше, на сколько, а лишь вывести на экран один из трех вариантов, а для простоты из двух. Вариант 1 Допустим у нас есть массив из двух элементов [”А больше чем Б”,”Б больше чем А”]. [...]
декабря 14, 2006 в 19:22
А сейчас есть? сам не понял что там произошло… почемуто как приватное пометилось.