kak mozno napechata 100000 raz "welcome" ne ispolzya loop?
От: kosfr Израиль  
Дата: 19.01.05 12:11
Оценка:
byl ya na sobesedovanii na raboty c++/C#.
zadali vopros: kak napisat ne vazno na kakomyazuke 1.000.000 raz "Welcome" ne ispolzya: goto, for, while, do-while etc. parvui sposob recyrsia, a vtoroi????

18.02.05 15:11: Перенесено из 'Алгоритмы'
Kostya
Re: kak mozno napechata 100000 raz "welcome" ne ispolzya loo
От: tarkil Россия http://5209.copi.ru/
Дата: 19.01.05 12:16
Оценка:
Здравствуйте, kosfr, Вы писали:

K>zadali vopros: kak napisat ne vazno na kakomyazuke 1.000.000 raz "Welcome" ne ispolzya: goto, for, while, do-while etc. parvui sposob recyrsia, a vtoroi????


Ах, без goto... Ну, можно написать программу, которая сгенерирует миллион строчек printf

Без рекурсии тут, по-моему, никак...
--
wbr, Peter Taran
Re: kak mozno napechata 100000 raz "welcome" ne ispolzya loo
От: tacit_one Россия  
Дата: 19.01.05 12:21
Оценка: 1 (1) +1 :))) :))) :))) :))
Здравствуйте, kosfr, Вы писали:

K>byl ya na sobesedovanii na raboty c++/C#.

K>zadali vopros: kak napisat ne vazno na kakomyazuke 1.000.000 raz "Welcome" ne ispolzya: goto, for, while, do-while etc. parvui sposob recyrsia, a vtoroi????

main() {
    printf( "1.000.000 raz 'Welcome'" );
}
Re: kak mozno napechata 100000 raz "welcome" ne ispolzya loo
От: Unforgiver Россия  
Дата: 19.01.05 12:22
Оценка: +2
Здравствуйте, kosfr, Вы писали:

K>byl ya na sobesedovanii na raboty c++/C#.

K>zadali vopros: kak napisat ne vazno na kakomyazuke 1.000.000 raz "Welcome" ne ispolzya: goto, for, while, do-while etc. parvui sposob recyrsia, a vtoroi????

Console.Writeln ("Welcome");

Copy-Paste 1.000.000 раз

Таймер сделай.
Всё заканчивается плохо. Если что-то закончилось хорошо — значит оно еще не закончилось.
Re: kak mozno napechata 100000 raz "welcome" ne ispolzya loo
От: Nev0 Россия  
Дата: 19.01.05 12:24
Оценка: 111 (16) +1
Здравствуйте, kosfr, Вы писали:

K>byl ya na sobesedovanii na raboty c++/C#.

K>zadali vopros: kak napisat ne vazno na kakomyazuke 1.000.000 raz "Welcome" ne ispolzya: goto, for, while, do-while etc. parvui sposob recyrsia, a vtoroi????

Очень быстро: 2^20 = 1048576

Delphi:
var
    s: string;
begin
    s := 'Welcome';
    s := s + s;
    s := s + s;
    s := s + s;
    s := s + s;
    s := s + s;
    s := s + s;
    s := s + s;
    s := s + s;
    s := s + s;
    s := s + s;
    s := s + s;
    s := s + s;
    s := s + s;
    s := s + s;
    s := s + s;
    s := s + s;
    s := s + s;
    s := s + s;
    s := s + s;
    s := s + s;
    writeln(s);
end.
Re[2]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: kosfr Израиль  
Дата: 19.01.05 12:28
Оценка:
Здравствуйте, tacit_one, Вы писали:

_>Здравствуйте, kosfr, Вы писали:


K>>byl ya na sobesedovanii na raboty c++/C#.

K>>zadali vopros: kak napisat ne vazno na kakomyazuke 1.000.000 raz "Welcome" ne ispolzya: goto, for, while, do-while etc. parvui sposob recyrsia, a vtoroi????

_>
_>main() {
_>    printf( "1.000.000 raz 'Welcome'" );
_>}
_>


klass
Kostya
Re[2]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: Nev0 Россия  
Дата: 19.01.05 12:36
Оценка: 20 (3)
N>Очень быстро: 2^20 = 1048576
Поправка, если учитывать разложение 1000000 = 11110100001001000000
то получится следующий код из ~20 строк.
Delphi:
var
    s: string;
begin
    s := 'Welcome'#10; 
    s := s + s;            
    s := s + s;            
    s := s + s;      
    s := s + s;      
    s := s + s;     
    s := s + s; write(s);
    s := s + s;
    s := s + s;
    s := s + s; write(s);
    s := s + s;
    s := s + s;
    s := s + s;
    s := s + s;
    s := s + s; write(s);
    s := s + s;
    s := s + s; write(s);
    s := s + s; write(s);
    s := s + s; write(s);
    s := s + s; write(s);
end.

В итоге ровно 1000000 строк Welcome
Re[3]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: kosfr Израиль  
Дата: 19.01.05 12:45
Оценка:
Здравствуйте, Nev0, Вы писали:

N>>Очень быстро: 2^20 = 1048576

N>Поправка, если учитывать разложение 1000000 = 11110100001001000000
N>то получится следующий код из ~20 строк.
N>Delphi:
N>
N>var
N>    s: string;
N>begin
N>    s := 'Welcome'#10; 
N>    s := s + s;            
N>    s := s + s;            
N>    s := s + s;      
N>    s := s + s;      
N>    s := s + s;     
N>    s := s + s; write(s);
N>    s := s + s;
N>    s := s + s;
N>    s := s + s; write(s);
N>    s := s + s;
N>    s := s + s;
N>    s := s + s;
N>    s := s + s;
N>    s := s + s; write(s);
N>    s := s + s;
N>    s := s + s; write(s);
N>    s := s + s; write(s);
N>    s := s + s; write(s);
N>    s := s + s; write(s);
N>end.
N>

N>В итоге ровно 1000000 строк Welcome

prikolno.
Kostya
Re: kak mozno napechata 100000 raz "welcome" ne ispolzya loo
От: Кодт Россия  
Дата: 19.01.05 13:21
Оценка: 67 (11)
Здравствуйте, kosfr, Вы писали:

K>byl ya na sobesedovanii na raboty c++/C#.

K>zadali vopros: kak napisat ne vazno na kakomyazuke 1.000.000 raz "Welcome" ne ispolzya: goto, for, while, do-while etc. parvui sposob recyrsia, a vtoroi????

Развернуть рекурсию через шаблон.

Рекурсия, кстати, тоже разная бывает...
void hello_linear(unsigned n)
{
  printf("welcome\n");
  if(--n)
    hello_linear(n); // выжрем стек к чёртовой матери
}

void hello_log2(unsigned n)
{
  if(n % 2) printf("welcome\n");
  n /= 2;
  if(n)
  {
    hello_log2(n);
    hello_log2(n);
  }
}

void hello_log3(unsigned n)
{
  switch(n % 3)
  {
  case 2: printf("welcome\n"); /*nobreak*/
  case 1: printf("welcome\n"); /*nobreak*/
  }
  n/=3;
  if(n)
  {
    hello_log3(n);
    hello_log3(n);
    hello_log3(n);
  }
}

Если заменить %2 и /=2 на &1 и <<=1, то станет видно, что двоично-логарифмический способ — это не что иное, как проверка битов.

Кстати, фокус с суммированием строки — очень коварный.
Во-первых, требуется 800000 байт памяти, во-вторых, его "наивная" реализация приведёт к жутким тормозам — до O(N^2).

... а вот и шаблон
template<unsigned N> struct hello
{
  static doit() { hello<N%2>::doit(); hello<N/2>::doit(); hello<N/2>::doit(); }
};
template<> struct hello<1>
{
  static doit() { printf("welcome\n"); }
};
template<> struct hello<0>
{
  static doit() {}
};
Перекуём баги на фичи!
Re: kak mozno napechata 100000 raz "welcome" ne ispolzya loo
От: Stanky  
Дата: 19.01.05 15:39
Оценка:
dwCounter    dd    1

PrintWelcome    proc
    cmp    [dwCounter],1000
    je     @@LastPrint
    push   offset PrintWelcome
@@LastPrint:
    ;Вывод строки "Welcome"
    inc    [dwCounter]
    ret
PrintWelcome    endp
Posted via RSDN NNTP Server 1.9
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Re[2]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: Stanky  
Дата: 20.01.05 11:49
Оценка: +1
Хочу прояснить саму идею: когда вызывается какая-то функция, то в стек заносится адрес возврата (адрес команды следующий за командой вызова)!!! Лубая функция завершается коммандой ret, которая передаёт управление по адресу, находящемуся в вершине стека (ss:esp/sp) и "удаляет" это значение из стека!!! В примере, что я привёл делается следующие: есть счётчик в котором хранится номер вывода (в нашем случаем от 1 до 1000) и если этот счётчик не достиг конечного значения, то кладём в стек адрес начала функции PrintWelcome и соответственно команда ret вернёт нас не туда откуда мы в эту функцию пришли, а в неё самую!!! Когда счётчик достигнет конечного значения, то в стек ничего не кладём, соответственно ret получит адрес возврата из функции!!!
В отличии от рекурсии при таком подходе мы никогда не выжрем стек, соответственно вызовов может быть хоть 1000000000 и всё будет пучком!!!

Надеюсь это то, что ты и хотел получить!!!
Posted via RSDN NNTP Server 1.9
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Re[3]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: Кодт Россия  
Дата: 20.01.05 12:16
Оценка:
Здравствуйте, Stanky, Вы писали:

S>Хочу прояснить саму идею: когда вызывается какая-то функция, то в стек заносится адрес возврата (адрес команды следующий за командой вызова)!!! Лубая функция завершается коммандой ret, которая передаёт управление по адресу, находящемуся в вершине стека (ss:esp/sp) и "удаляет" это значение из стека!!! В примере, что я привёл делается следующие: есть счётчик в котором хранится номер вывода (в нашем случаем от 1 до 1000) и если этот счётчик не достиг конечного значения, то кладём в стек адрес начала функции PrintWelcome и соответственно команда ret вернёт нас не туда откуда мы в эту функцию пришли, а в неё самую!!! Когда счётчик достигнет конечного значения, то в стек ничего не кладём, соответственно ret получит адрес возврата из функции!!!

S>В отличии от рекурсии при таком подходе мы никогда не выжрем стек, соответственно вызовов может быть хоть 1000000000 и всё будет пучком!!!

S>Надеюсь это то, что ты и хотел получить!!!


Во-первых, здесь реализован цикл с декрементом счётчика (а в задании есть ограничение на циклы)
Во-вторых, это всего лишь вариация на тему setjmp/longjmp — всего лишь вычурная форма goto (а на него тоже есть ограничения)
Вот как это можно было бы сделать на Си:
int count=100000;
jmp_buf env;
setjmp(env);
printf("welcome");
if(--count) longjmp(env,0);
Перекуём баги на фичи!
Re: kak mozno napechata 100000 raz "welcome" ne ispolzya loo
От: sercher Украина  
Дата: 20.01.05 15:12
Оценка: 434 (42) :))) :)))
Здравствуйте, kosfr, Вы писали:

K>byl ya na sobesedovanii na raboty c++/C#.

K>zadali vopros: kak napisat ne vazno na kakomyazuke 1.000.000 raz "Welcome" ne ispolzya: goto, for, while, do-while etc. parvui sposob recyrsia, a vtoroi????


class Welcome
{
  public:
   Welcome() {cout<<"Welcome!\n";}

}

int main()
{
  Welcom arr[1000000];
}


Re[4]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: Stanky  
Дата: 20.01.05 16:22
Оценка:
> Во-первых, здесь реализован цикл с декрементом счётчика (а в задании
> есть ограничение на циклы)
>
Не понял, можно разъяснить?

> Во-вторых, это всего лишь вариация на тему setjmp/longjmp — всего лишь

> вычурная форма goto (а на него тоже есть ограничения)
>
Тогда получается, что кроме goto в процах вообще ничего нет!!!
Ведь та же рекурсия (вызов функции) организуется через команду call, а это тотже goto (jmp) только в стек записывается адрес возврата!!!
Posted via RSDN NNTP Server 1.9
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Re[5]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: sercher Украина  
Дата: 20.01.05 16:26
Оценка:
S>Тогда получается, что кроме goto в процах вообще ничего нет!!!
S>Ведь та же рекурсия (вызов функции) организуется через команду call, а это тотже goto (jmp) только в стек записывается адрес возврата!!!

К чему споры, задание было на C++ или C#
Re[6]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: Stanky  
Дата: 20.01.05 17:38
Оценка:
> К чему споры, задание было на C++ или C#
>
Цитирую:
zadali vopros: kak napisat ne vazno na kakomyazuke
Posted via RSDN NNTP Server 1.9
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Re[6]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: Stanky  
Дата: 20.01.05 17:52
Оценка:
Я конечно понимаю, что это не чистый C'шник, но...
#include <stdio.h>

unsigned int Counter = 0;


PrintWelcome()
{
Print:
    if (++Counter == 1000)
    {
        Counter = 0;
    }
    else
    {
        __asm
        {
            push offset Print
            //Необходимо для Windows
            push ebp
            mov ebp,esp
            sub esp,12
        }
    }
    printf("Welcome\n");
}


main()
{
    PrintWelcome();
}
Posted via RSDN NNTP Server 1.9
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Re[2]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: Аноним  
Дата: 20.01.05 17:56
Оценка: 75 (9) :))) :))) :))) :)
Классно!
Небольшая оптимизация

class Welcome
{
  public:
   Welcome() {cout<<"Welcome!\n";}
   ~Welcome() {cout<<"Welcome!\n";}

}

int main()
{
  Welcom arr[500000];
}
Re[2]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: tarkil Россия http://5209.copi.ru/
Дата: 21.01.05 03:27
Оценка:
Здравствуйте, sercher, Вы писали:

S>int main()

S>{
S> Welcom arr[1000000];
S>}
S>[/ccode]

Блеск!
--
wbr, Peter Taran
Re: kak mozno napechata 100000 raz "welcome" ne ispolzya loo
От: Костя Ещенко Россия  
Дата: 21.01.05 05:02
Оценка: 7 (1)
Здравствуйте, kosfr, Вы писали:

K>byl ya na sobesedovanii na raboty c++/C#.

K>zadali vopros: kak napisat ne vazno na kakomyazuke 1.000.000 raz "Welcome" ne ispolzya: goto, for, while, do-while etc. parvui sposob recyrsia, a vtoroi????

Можно вызвать внешнюю функцию, которая сделает это за нас:
#include <iostream>
#include <algorithm>

int main()
{
  using namespace std;
  fill_n( ostream_iterator<char const*>(cout), 1000000, "Welcome " );
}
На самом деле, люди не читают газеты, они принимают их каждое утро, так же как ванну. ©Маршалл Мак-Льюэн
Re[5]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: Кодт Россия  
Дата: 21.01.05 13:20
Оценка:
Здравствуйте, Stanky, Вы писали:

>> Во-первых, здесь реализован цикл с декрементом счётчика (а в задании

>> есть ограничение на циклы)
>>
S>Не понял, можно разъяснить?

Очень просто. Давай вместо push/ret напишем человеческое goto. Получится цикл.

>> Во-вторых, это всего лишь вариация на тему setjmp/longjmp — всего лишь

>> вычурная форма goto (а на него тоже есть ограничения)
>>
S>Тогда получается, что кроме goto в процах вообще ничего нет!!!
S>Ведь та же рекурсия (вызов функции) организуется через команду call, а это тотже goto (jmp) только в стек записывается адрес возврата!!!

Это лишь один из способов организовать рекурсию.
Языки обработки символов списков (тот же Лисп) могут делать это по-другому.
Например, выполнять подстановку тела функции в выражение, и последовательно интерпретировать.
Перекуём баги на фичи!
Re[6]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: Stanky  
Дата: 21.01.05 22:07
Оценка:
> Очень просто. Давай вместо push/ret напишем человеческое goto.
>
Ну без команд перехода не обойтись вообще, так как даже if, switch/case, вызов функций, прерываний и т. д. их использует!!!
Так что получается, что задача просто нерешаемая!!!
Posted via RSDN NNTP Server 1.9
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Re[3]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: Аноним  
Дата: 21.01.05 22:26
Оценка: 3 (1)
Здравствуйте, Аноним, Вы писали:

А>Классно!

А>Небольшая оптимизация

А>
А>class Welcome
А>{
А>  public:
А>   Welcome() {cout<<"Welcome!\n";}
А>   ~Welcome() {cout<<"Welcome!\n";}

А>}

А>int main()
А>{
А>  Welcom arr[500000];
А>}
А>


Ну и наконец, если мы напишем так:
Welcom *arr = new Welcom[500000];
delete []arr;

то избавляем себя от возможных проблем с переполнением стека
В общем нету предела совершенства
Re: kak mozno napechata 100000 raz "welcome" ne ispolzya loo
От: Dimonka Верблюд  
Дата: 24.01.05 15:06
Оценка:
Здравствуйте, kosfr, Вы писали:

K>byl ya na sobesedovanii na raboty c++/C#.

K>zadali vopros: kak napisat ne vazno na kakomyazuke 1.000.000 raz "Welcome" ne ispolzya: goto, for, while, do-while etc. parvui sposob recyrsia, a vtoroi????

Print RepeatString(1000000, "Welcome")

Re[7]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: Кодт Россия  
Дата: 25.01.05 13:17
Оценка:
Здравствуйте, Stanky, Вы писали:

S>Ну без команд перехода не обойтись вообще, так как даже if, switch/case, вызов функций, прерываний и т. д. их использует!!!

S>Так что получается, что задача просто нерешаемая!!!

Шаблонное программирование — может развернуть всё в один длинный-предлинный код (100000 раз повторит printf("welcome")). Потому что инлайн.

Разумеется, будем считать вызов printf атомарным. А почему бы и нет? Может, это инструкция для DMA-контроллера?..
Перекуём баги на фичи!
Re[2]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: Аноним  
Дата: 25.01.05 17:06
Оценка: :))
a ya nashol reshenia poproshche
nujno obedinit 1000000 kompiuterov v set i potom v command prompte napechatat net send all welcome
i vsio
Re[3]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: Ka3a4oK  
Дата: 23.02.05 06:10
Оценка:
круто.
... << RSDN@Home 1.1.4 beta 4 rev. 303>>
Re: kak mozno napechata 100000 raz "welcome" ne ispolzya loo
От: Erop Россия  
Дата: 07.04.05 18:06
Оценка:
Здравствуйте, kosfr, Вы писали:

K>byl ya na sobesedovanii na raboty c++/C#.

K>zadali vopros: kak napisat ne vazno na kakomyazuke 1.000.000 raz "Welcome" ne ispolzya: goto, for, while, do-while etc. parvui sposob recyrsia, a vtoroi????

Скомпилировать


template<int count>
class WW {
public:    
    static void DoIt()
    {
        int Welcome;
        WW<count - 1>::DoIt();
    }
};


template<>
class WW<0> {
public:
    static void DoIt() {}
};

static int f()
{
    WW<1000 * 1000>::DoIt();
}






Правлда я рискнул попробовать только 100 раз напечатать
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[2]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: Кодт Россия  
Дата: 07.04.05 18:17
Оценка:
Здравствуйте, Erop, Вы писали:

E>Правлда я рискнул попробовать только 100 раз напечатать


Конечно! Между тем, есть действенный вариант с шаблонами. См. выше по ветке...
Перекуём баги на фичи!
Re[3]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: Erop Россия  
Дата: 07.04.05 22:31
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Конечно! Между тем, есть действенный вариант с шаблонами. См. выше по ветке...


Конечно есть, правда это не совсем соответсвует заданию, что типа не рекурсия
Но зато прикольно, что можно печатать не в stdout, скажем, а влог компиляции )
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[2]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: fulltick  
Дата: 08.04.05 02:19
Оценка:
Здравствуйте, Erop, Вы писали:

E>Скомпилировать

E>Правлда я рискнул попробовать только 100 раз напечатать
Не компилируется —
> fatal error C1204: compiler limit : internal structure overflow
Re[3]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: Erop Россия  
Дата: 08.04.05 04:33
Оценка:
Здравствуйте, fulltick, Вы писали:

F>Не компилируется —

>> fatal error C1204: compiler limit : internal structure overflow


А что за компилятор и какое число повторов ставил?

На самом деле, если кто-то не заметил, эта штука печатает Welcome не при работе, а при компиляции
В предупреждениеях о неиспользуемой переменной Welcome
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[4]: kak mozno napechata 100000 raz "welcome" ne ispolzya
От: fulltick  
Дата: 08.04.05 04:39
Оценка:
Здравствуйте, Erop, Вы писали:

E>А что за компилятор

Visual C++ 7.1

E>и какое число повторов ставил?

1000000, как в примере

E>На самом деле, если кто-то не заметил, эта штука печатает Welcome не при работе, а при компиляции

E>В предупреждениеях о неиспользуемой переменной Welcome
Ну это я понял, просто интересно было посмотреть, что скажет компилятор.
Сообщения о не используемой переменной я задавил int Welcome = 0, а то компиляция длится д-о-о-о-о-о-о-о-лго.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.