Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 81, средняя оценка - 4.65
sergey1369
0 / 0 / 0
Регистрация: 02.03.2011
Сообщений: 6
#1

Как вывести числа от 1 до 1000 без сравнений в Си++? - C++

02.03.2011, 18:08. Просмотров 10262. Ответов 68
Метки нет (Все метки)

Привет всем.

Получил на собеседовании по Си++ такой странный вопрос, подумал, ещё подумал.
Ничего путного в голову не пришло. Вообщем стало дико любопытно, а как это
сделать средствами Си++?

Переадресую вопрос умным головам форума. Подскажите.

P.S. Человек с которым общался явно знал не менее двух решений.
Но я был не в том положении, чтобы спрашивать у него.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.03.2011, 18:08     Как вывести числа от 1 до 1000 без сравнений в Си++?
Посмотрите здесь:
C++ Вывести простые числа на интервале от 2 до 1000
Вывести числа, заканчивающиеся на 3 или 5, находящиеся в диапазоне от 1 до 1000 C++ Builder
C++ Вывести все целые числа, на которые оба введенных числа делятся без остатка
Даны числа от 1 до 1000 и число m. Вывести результат умножение куба нечетных сотен на число m C++
Как из числа double 4.056 извлечь число 1000? C++
подскажите: как вывести на экран числа от 0 до 20.... и еще одна: вывести все четные числа от 0 до 20... C++
вывести массив без максимального и минимального числа C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
16.03.2011, 01:56     Как вывести числа от 1 до 1000 без сравнений в Си++? #41
Цитата Сообщение от ValeryS Посмотреть сообщение
если мы сейчас говорим о сях
Цитата Сообщение от ValeryS Посмотреть сообщение
переменная типа bool
......
nxnx
Формучанин
362 / 293 / 16
Регистрация: 02.11.2010
Сообщений: 1,234
16.03.2011, 01:57     Как вывести числа от 1 до 1000 без сравнений в Си++? #42
Цитата Сообщение от Евгений М. Посмотреть сообщение
Вот и второе решение.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <stdlib.h>
 
void donothing() {}
 
void dosomething() {exit(0);}
 
int main()
{
    int i;
 
    void (*pf[2])() = {donothing, dosomething};
    
    for (i=1;; i++)
    {
        printf("%d\n", i);
        pf[i/1000]();
    }
}
вот этот код подойдёт. дизазм:
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
!        void (*pf[2])() = {donothing, dosomething};
main()
main+14: movl   $0x4013c0,0x14(%esp)
main+22: movl   $0x4013c5,0x18(%esp)
!
!        for (i=1;; i++)
main+30: movl   $0x1,0x1c(%esp)
main+89: incl   0x1c(%esp)
!        {
!                printf("%d\n", i);
main+38: mov    0x1c(%esp),%eax
main+42: mov    %eax,0x4(%esp)
main+46: movl   $0x40306c,(%esp)
main+53: call   0x401cd8 <printf>
!                pf[i/1000]();
main+58: mov    0x1c(%esp),%ecx
main+62: mov    $0x10624dd3,%eax
main+67: imul   %ecx
main+69: sar    $0x6,%edx
main+72: mov    %ecx,%eax
main+74: sar    $0x1f,%eax
main+77: mov    %edx,%ecx
main+79: sub    %eax,%ecx
main+81: mov    %ecx,%eax
main+83: mov    0x14(%esp,%eax,4),%eax
main+87: call   *%eax
!        }
main+93: jmp    0x4013fd <main+38>
нету ни cmp ни test ни loop ни j** (не считая jmp)
silent_1991
16.03.2011, 01:58
  #43

Не по теме:

Ладно, что-то я завёлся, видать, пора идти баиньки, а то мозг неадекватно на недосыпание реагирует...

ValeryS, замяли...

ValeryS
Модератор
6541 / 5007 / 461
Регистрация: 14.02.2011
Сообщений: 16,653
16.03.2011, 02:03     Как вывести числа от 1 до 1000 без сравнений в Си++? #44
Цитата Сообщение от nxnx Посмотреть сообщение
j**
условный переход
сравнение насколько я помню cmp
и еще раз повторю это для intel для других процессоров будет по другому
и даже если так
Assembler
1
2
dec eax
jnz .....
где здесь сравнение???

Добавлено через 3 минуты
самое смешное что если было бы число меньше 1000 допустим 10
компилятор мог спокойно развернуть цикл
nxnx
Формучанин
362 / 293 / 16
Регистрация: 02.11.2010
Сообщений: 1,234
16.03.2011, 02:05     Как вывести числа от 1 до 1000 без сравнений в Си++? #45
Цитата Сообщение от ValeryS Посмотреть сообщение
условный переход
сравнение насколько я помню cmp
и еще раз повторю это для intel для других процессоров будет по другому
и даже если так
Assembler
1
2
dec eax
jnz .....
где здесь сравнение???
неявное сравнение eax с нулём. аналогично:
Assembler
1
2
3
4
repeat:
 
......
loop repeat
//неявное сравнение ecx с нулём.
Но можно ли такое использовать под вопросом.
Сама операция сравнение делится на два этапа: команда меняющая флаги + j**

Добавлено через 1 минуту
Цитата Сообщение от ValeryS Посмотреть сообщение
компилятор мог спокойно развернуть цикл
возможно если както заставить компилятор это сделать, скажем через ключи оптимизации,
то это тоже будет решением.
ValeryS
Модератор
6541 / 5007 / 461
Регистрация: 14.02.2011
Сообщений: 16,653
16.03.2011, 02:17     Как вывести числа от 1 до 1000 без сравнений в Си++? #46
nxnx
а ты с оптимизацией прокомпилируй

Добавлено через 5 минут
Цитата Сообщение от nxnx Посмотреть сообщение
неявное сравнение eax с нулём. аналогично
при команде dec вычитается 1 и выставляются флаги(кто сказал что там что-то сравнивается)
может там какой-нибудь триггер переключается Ты знаешь схемотехнику Пентиума? я нет
поэтому утверждать что идет сравнение не могу
Почему тогда нет неявного сравнения с другим числом

Добавлено через 3 минуты
неявное сравнение с нулем это из человеческой логики
типа если регистр (не)равен 0 то переходим
по машинному если (не)установлен флаг
а флаг может установить кто угодно вплоть до записи в регистр флагов
nxnx
Формучанин
362 / 293 / 16
Регистрация: 02.11.2010
Сообщений: 1,234
16.03.2011, 02:19     Как вывести числа от 1 до 1000 без сравнений в Си++? #47
Цитата Сообщение от ValeryS Посмотреть сообщение
неявное сравнение с нулем это из человеческой логики
типа если регистр (не)равен 0 то переходим
по машинному если (не)установлен флаг
а флаг может установить кто угодно вплоть до записи в регистр флагов
Надо сделать допущение, что данная ветка решений для i386 совместимых процессоров.
Ибо большинство на них.
ValeryS
Модератор
6541 / 5007 / 461
Регистрация: 14.02.2011
Сообщений: 16,653
16.03.2011, 02:43     Как вывести числа от 1 до 1000 без сравнений в Си++? #48
Цитата Сообщение от nxnx Посмотреть сообщение
loop repeat
//неявное сравнение ecx с нулём.
еще вычитание

Добавлено через 14 минут
чей то навеяло

C++
1
2
3
4
5
for(int i=1000;;i--)
 {
 int k=1000/i;     // при 0 вылетит по исключению
 printf("%d",1001-i);
 }
nxnx
Формучанин
362 / 293 / 16
Регистрация: 02.11.2010
Сообщений: 1,234
16.03.2011, 02:48     Как вывести числа от 1 до 1000 без сравнений в Си++? #49
чтобы однозначно решить такую задачу, в условии нужно писать архитектуру и какие можно использовать инструкции, и в соотв с этим создавать код.
Сравнение это всётаки j**, поскольку test\cmp не всегда есть и они аналоги and\sub по флагам.
Но можно его представить как условный переход, тоже верно, в зависимости от логики программы.
gcc отказался разворачивать цикл кстати.

Добавлено через 1 минуту
я тоже думал про вариант с исключением, можно попытатся сделать так чтобы вылетало при попытке записать туда, куда нельзя записывать.

Добавлено через 3 минуты
но всётаки вариант с исключением это уже немного не то) хотя в нём нету ни j** ни cmp\test ни loop)
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
!      for( i=1000;;i--)
main()
main+14: movl   $0x3e8,0x1c(%esp)
main+61: decl   0x1c(%esp)
! {
! int k=1000/i;     // при 0 вылетит по исключению
main+22: mov    $0x3e8,%eax
main+27: cltd   
main+28: idivl  0x1c(%esp)
main+32: mov    %eax,0x18(%esp)
! printf("%d",1001-i);
main+36: mov    $0x3e9,%eax
main+41: sub    0x1c(%esp),%eax
main+45: mov    %eax,0x4(%esp)
main+49: movl   $0x40306c,(%esp)
main+56: call   0x401cb8 <printf>
! }
main+65: jmp    0x4013ed <main+22>
ValeryS
Модератор
6541 / 5007 / 461
Регистрация: 14.02.2011
Сообщений: 16,653
16.03.2011, 02:51     Как вывести числа от 1 до 1000 без сравнений в Си++? #50
Цитата Сообщение от nxnx Посмотреть сообщение
чтобы однозначно решить такую задачу, в условии нужно писать архитектуру и какие можно использовать инструкции, и в соотв с этим создавать код.
Не согласен
Ни каждый кто хорошо знает С С++ хорошо знает ассемблер.
тем более во что превратится его код
надо задавать уровень абстракции например
не использовать < , > ==, и т.д.
или не использовать циклы
или рекурсии
или ни того не другого

Добавлено через 1 минуту
кстати исключение можно и в рекурсию запихнуть
nxnx
Формучанин
362 / 293 / 16
Регистрация: 02.11.2010
Сообщений: 1,234
16.03.2011, 02:52     Как вывести числа от 1 до 1000 без сравнений в Си++? #51
Цитата Сообщение от ValeryS Посмотреть сообщение
Не согласен
Ни каждый кто хорошо знает С С++ хорошо знает ассемблер.
тем более во что превратится его код
надо задавать уровень абстракции например
не использовать < , > ==, и т.д.
или не использовать циклы
или рекурсии
или ни того не другого
либо так, либо как я написал. Ибо изначальное условие поставлено размыто.
ValeryS
Модератор
6541 / 5007 / 461
Регистрация: 14.02.2011
Сообщений: 16,653
16.03.2011, 02:53     Как вывести числа от 1 до 1000 без сравнений в Си++? #52
Цитата Сообщение от nxnx Посмотреть сообщение
gcc отказался разворачивать цикл кстати.
попробую завтра на VS
Evg
Эксперт CАвтор FAQ
17469 / 5707 / 362
Регистрация: 30.03.2009
Сообщений: 15,664
Записей в блоге: 26
16.03.2011, 17:48     Как вывести числа от 1 до 1000 без сравнений в Си++? #53
Хорошая задача. По крайней мере половина красоты задачи состоит в том, что на одной только формулировке "без сравнений" можно отсеять приличный процент нешарящих людей.
ValeryS
Модератор
6541 / 5007 / 461
Регистрация: 14.02.2011
Сообщений: 16,653
16.03.2011, 19:47     Как вывести числа от 1 до 1000 без сравнений в Си++? #54
Visual C 2008
тоже не захотел разворачивать цикл
причем
for(int i=0;i<1;i++)
честно выкинул цикл
а уже при 2 создал цикл как я его не упрашивал
Посему вопрос
Могут ли компиляторы разворачивать циклы или это фантастика??
хотя цикл
for(int i=0;i<10;i++)
m+=i;
по моему все компиляторы выбросят
Coin
0 / 0 / 0
Регистрация: 12.04.2008
Сообщений: 14
16.03.2011, 20:53     Как вывести числа от 1 до 1000 без сравнений в Си++? #55
Цитата Сообщение от ValeryS Посмотреть сообщение
Могут ли компиляторы разворачивать циклы или это фантастика??
собери icc он развернет.
Evg
Эксперт CАвтор FAQ
17469 / 5707 / 362
Регистрация: 30.03.2009
Сообщений: 15,664
Записей в блоге: 26
16.03.2011, 21:40     Как вывести числа от 1 до 1000 без сравнений в Си++? #56
Цитата Сообщение от ValeryS Посмотреть сообщение
Могут ли компиляторы разворачивать циклы или это фантастика??
Могут, если включить оптимизации. Причём разные компиляторы на разных архитектурах будут себя вести по разному. Есть опции тонкой настройки, отвечающие за такие оптимизации: ведь разворачнивание цикла (loop unroll) с одной стороны ведёт к ускорению кода, с другой - к увеличению в размерах
ValeryS
Модератор
6541 / 5007 / 461
Регистрация: 14.02.2011
Сообщений: 16,653
16.03.2011, 22:04     Как вывести числа от 1 до 1000 без сравнений в Си++? #57
Я догадываюсь зачем разворачивают цикл
Ho nxnx на gcc, а я на VS не смог
хотя включал и быстрый код и оптимизацию по скорости
Поэтому и возник вопрос
Evg
Эксперт CАвтор FAQ
17469 / 5707 / 362
Регистрация: 30.03.2009
Сообщений: 15,664
Записей в блоге: 26
16.03.2011, 22:10     Как вывести числа от 1 до 1000 без сравнений в Си++? #58
Так просто разные настройки по дефолту. Надо опции компилятора смотреть
ValeryS
Модератор
6541 / 5007 / 461
Регистрация: 14.02.2011
Сообщений: 16,653
16.03.2011, 22:33     Как вывести числа от 1 до 1000 без сравнений в Си++? #59
Где ж их смотреть то???
MSDN
Параметр /Ot (предпочитать скорость кода) максимизирует скорость EXE-файлов и библиотек DLL, указывая компилятору предпочесть скорость кода его краткости (это установка по умолчанию). Компилятор может сократить многие конструкции C и C++, преобразовав их в аналогичные по функциональности последовательности машинного кода. Иногда различия между ними предлагают выбор между краткостью или скоростью. Параметр /Ot подразумевается параметром "Максимальная скорость" (/O2/O1, /O2 (минимизировать размер, максимизировать скорость)). Параметр /O2 объединяет несколько возможностей по созданию очень быстрого кода.
и еще
Оптимизация цикла

При этом виде оптимизации неизменяемые части выражения удаляются из тела цикла. Оптимальный цикл включает только те выражения, значения которых изменяются при каждом выполнении цикла. В следующем примере выражение x + y в теле цикла не меняется:

Копировать код
i = -100;
while( i < 0 ) {
i += x + y;
}


После оптимизации вычисление значения для выражения x + y выполняется однократно, а не при каждом выполнении цикла:

Копировать код
i = -100;
t = x + y;
while( i < 0 ) {
i += t;
}
про развертывание ни слова

Добавлено через 1 минуту
кстати плохой пример этот цикл должен выкинутся и добавится константа

Добавлено через 4 минуты
пардон ступил
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.03.2011, 05:17     Как вывести числа от 1 до 1000 без сравнений в Си++?
Еще ссылки по теме:
C++ Вывести числа в диапазоне от 0 до 500.которые делятся на 5 без остатка
Вывести в цикле те цифры числа, которые не делятся на 3 без остатка. C++
Без операторов цикла вывести цифры числа через пробел C++
C++ Сколько сравнений понадобится в худшем случае, чтобы упорядочить по возрастанию 4 различных числа
Вывести на экран все числа, на которые заданное число делится без остатка C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
alex_x_x
бжни
2445 / 1650 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
17.03.2011, 05:17     Как вывести числа от 1 до 1000 без сравнений в Си++? #60
притянуто конечно..

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <vector>
#include <iostream>
 
int main()
{
  std::vector<int> v( 1000 );
  try 
  { 
     for( int i=0; ;++i )
     {
       v.at( i );
       std::cout << i+1 << " "; 
     }    
   }
   catch(...)
   {
  
   }     
}
Yandex
Объявления
17.03.2011, 05:17     Как вывести числа от 1 до 1000 без сравнений в Си++?
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru