Cool Folders ® :: Форум Игротека :: Задачка для программистов

Дата : 13-08-05, Сбт, 01:54:49

Сразу предупреждаю, у этой задачи скорее всего нету решения.
Но я не уверен и поэтому я здесь

Я правильного решения не нашел

Итак:
Язык С.
Напишите рекурсивную функцию которая принимает ОДИН параметр N
и ресует два прямых треугольника. Один противоположный другому.
звездочками естественно

N - максимальное количество звездочек в одной строке.
Пример: Для N = 4:
*
**
***
****
****
***
**
*

Условия:
Для решения данной задачи нельзя пользоваться (циклами) FOR/While и т.д
Но можно написать и использовать ОДНУ вспомогательную функцию.
На данном этапе у задачи есть решение.
Но есть еще одно условие которое я поставлю после того как кто нибудь решит эту задачу в данном варианте

Взято из << Домашнего задания для Студнтов "Тохна" в Колледже Брауда (Кармиэель) "Хороший такой колледж" 2 Семестр. Профессор задавшая данную задачу не захотела показать правильное решение.>>

Выбор всегда остается за нами. Всегда - за нами. Мы идем вперед, мы торопимся, но хватит ли нам отваги прервать движение, остановится, превозмогая страх, и повернутся спиной к опасности или счастью, которые всегда впереди, и лицом к выбору, который всегда, вечно, неумолимо и невидимо остается за нами. (ц.) H.L.Oldie

Задачка для программистов

№ 2

yxo

Дата : 13-08-05, Сбт, 12:57:35

Пример проги: (даже не поленился раскрасить

)

#include <stdio.h>

void asterik(int n) {
if (n == 0) {
    printf("\n" );
    return;
}

if (n < 0) {
    printf("*" );
    asterik(n+1);
} else {
    printf("*" );
    asterik(n-1);
}
}

void draw(int n) {
static int start = 0;
static int stop = 0;

if (start == 0) {
    start = n;
    stop = -n;
}

if ((n < 0) && (n >= stop)) {
   asterik(n);
   draw(n+1);
}

if (n > 0) {
    draw(n-1);
    asterik(n);
}

if (n == start) {
    n = stop;
    draw(n);
}
}

int main() {
draw(10);
}

На STDOUT выдаёт для 10:
*
**
***
****
*****
******
*******
********
*********
**********
**********
*********
********
*******
******
*****
****
***
**
*

...и днем и ночью

учёный всё ходит по цепи кругом...
[ 13-08-05, Сбт, 20:00:32 Отредактировано: yxo ]

Задачка для программистов

№ 3

Дата : 13-08-05, Сбт, 13:18:20

Замени первый вызов asterik (n) (в if ((n < 0) && (n >= stop)) на asterik(-n) и тогда функцию asterik можно сократить в два раза

Но со static-ами неинтересно.. Это сродни глобальным переменным.. Т.е. по сути получается, что функция draw работает не с одним параметром, а с тремя...

А вот сделать действительно с одним параметром и без статик-ов?

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

Задачка для программистов

№ 4

Дата : 13-08-05, Сбт, 14:02:00

Вот это и есть последнее условие.

Без статичных и без глобальных переменных.
Но я все таки думаю что такого решения нет.

Вот кстати мое решение со static-ом:
void printStars(int nStars)
{
   if (nStars==0)
   {
      printf("\n" );
      return;
   }
   printf("*" );
   printStars(nStars-1);
}

void printME(int n)
{
   static int nMax = 0;
   if (nMax == 0)
   {
         nMax = n;
         n=1;
   }

    if (n > nMax)
      return;

   printStars(n);
   printME(n+1);
   printStars(n);
}

int main() {
   printME(10);
   return 0;
}

ПС: Грызь, а слабо кнопку сделать для цитирования кода?

ПС2: А может кто нибудь сюда еще таких задачек подкинет?

Задачка для программистов

№ 5

Дата : 13-08-05, Сбт, 14:04:40

Gunslinger, т.е. можно пользоваться одной вспомогательной функцией, но нельзя пользоваться глобальными и статическими?
А есть ограничение на кол-во параметров во вспомогательной функции? И обязательно ли главная функция должна быть рекурсивной?

А то, если на оба вопроса ответ "необязательно", то решение почти примитивное

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

Задачка для программистов

№ 6

Дата : 13-08-05, Сбт, 14:07:21

ПС: Грызь, а слабо кнопку сделать для цитирования кода?

В смысле?

ПС2: А может кто нибудь сюда еще таких задачек подкинет?

Да запросто

Я их и сам выдумывал когда-то..

Вот только решу эту задачу и подкину новую.

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

Задачка для программистов

№ 7

Дата : 13-08-05, Сбт, 14:10:13

не не катит.
я тоже сначала подумал зделать одну такую функцию:
printMain(int N)
{
DoPrint(1,N);
}

но главная функция та которая принимает N - должна быть рекурсивной.
а насчет вспомагательной - ограничений на количество параметров нет.

Задачка для программистов

№ 8

Дата : 13-08-05, Сбт, 14:11:33

Буем думать.

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

Задачка для программистов

№ 9

Дата : 13-08-05, Сбт, 14:12:38

В смысле что бы не трогал пробелы в коде.
и синтаксис подсвечивал сам.

Задачка для программистов

№ 10

Дата : 13-08-05, Сбт, 14:16:51

Ну, с подсвечиванием синтаксиса - это за рамками

А то сегодня будем подсвечивать С/С++, а завтра - Visual Basic, FoxPro и MatLab. Где я наберу таблицы со списком зарезервированных слов..

Пробелы для табуляции - ставьте по три пробела (они сконвертируются в &nbsр;&nbsр;&nbsр; - т.е. будут именно тремя пробелами).

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

Задачка для программистов

№ 11

yxo

Дата : 13-08-05, Сбт, 14:45:48

ВСЁ СТЕР

..... не отвечает условиям. Будем думать. Но уже завтра.

...и днем и ночью

учёный всё ходит по цепи кругом...
[ 13-08-05, Сбт, 21:47:35 Отредактировано: yxo ]

Задачка для программистов

№ 12

Дата : 13-08-05, Сбт, 16:07:41

Аха, ухо

именно такое решение я и написал с самого начала

В смысле - принцип тот же, реализация чуток отличается.. Но тогда главная функция не имеет ничего общего с рекурсией..

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

Задачка для программистов

№ 13

Дата : 13-08-05, Сбт, 20:06:59

#include <stdio.h>

void asterik(int n)
{
   if (n>0)
   {
      printf("*" );
      asterik(n-1);
   }
   else
      printf("\n" );
}

void draw(int n)
{
   if (n>0)
   {
      draw(-2*n);
      draw(-2*n-1);
   }
   else if (n<0 && n%2==0)
   {
      draw(n+2);
      asterik(-n/2);
   }
   else if (n<-1 && n%2!=0)
   {
      asterik(-n/2);
      draw(n+2);
   }
}

int main() {draw(10);}

Жизнь - игра на ациклическом графе, а свобода - позиция, для которой есть >1 стратегии выигрыша.

Задачка для программистов

№ 14

Дата : 13-08-05, Сбт, 23:18:35

УиМ, угу... но я такое забраковал.. Потому что из-за умножения может не поместиться в int.

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

Задачка для программистов

№ 15

Дата : 14-08-05, Вск, 00:27:32

Если вспомогательная может иметь больше 1 параметра, то решение тривиально.

Жизнь - игра на ациклическом графе, а свобода - позиция, для которой есть >1 стратегии выигрыша.

Задачка для программистов

№ 16

Дата : 14-08-05, Вск, 00:36:20

Может иметь и больше

Какое решение?

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

Задачка для программистов

№ 17

Дата : 14-08-05, Вск, 00:53:29

Да можно обойтись и 1 параметром.

Основная функция при отрицательном n просто печатает n звёздочек (рекурсивно).
Вспомогательная функция печатает верхний или нижний треугольник в зависимости от знака n.

Жизнь - игра на ациклическом графе, а свобода - позиция, для которой есть >1 стратегии выигрыша.

Задачка для программистов

№ 18

Дата : 14-08-05, Вск, 00:57:53

Нарисуй

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

Задачка для программистов

№ 19

yxo

Дата : 14-08-05, Вск, 02:18:13

Что ? Совсем тривиальное ?!.... Переквалифицироваться надо

. Грызь ! Пошли цветочки собирать, а ?

К сабжу: УиМ ! Н А Р И С У Й !

Кстати, для чиска N в n бит, задачу можно решить с помощью регистра в 2n бит:
1. Копируем n бит числа N в 2 старших байта регистра А (размером в 2n) и в
   2 младших байта этого-же регистра.
2. В функции draw() рисуем звездочки (вызываем asterik()), уменьшая 2 нижних байта А
   на один, пока они не обнулятся.
3. После обнуления двух нижних байтов, переходим к двум верхним, уменьшая их на один
   в каждом рекурсивном проходе функции draw(). Звёздочки, естественно, рисуем в
   обратном порядке (к пункту 2).

Как ?

...и днем и ночью

учёный всё ходит по цепи кругом...

Задачка для программистов

№ 20

Дата : 14-08-05, Вск, 02:30:26

Автор: yxo
Дата : 14-08-05, Вск, 09:18:13

Кстати, для чиска N в n бит, задачу можно решить с помощью регистра в 2n бит:

Моя программа (пост № 13) требует всего лишь 1 лишний бит - и то Грызь боится, что не влезет в int.

Жизнь - игра на ациклическом графе, а свобода - позиция, для которой есть >1 стратегии выигрыша.

Задачка для программистов

№ 21

Дата : 14-08-05, Вск, 02:40:09

#include <stdio.h>

void draw(int n);

void triangle(int n)
{
   if (n>0)
   {
      triangle(n-1);
      draw(-n);
   }
   else if (n<0)
   {
      draw(n);
      triangle(n+1);
   }
}

void draw(int n)
{
   if (n<0)
   {
      printf("*" );
      draw(n+1);
   }
   else if (n == 0)
      printf("\n" );
   else
   {
      triangle(n);
      triangle(-n);
   }
}

int main() {draw(10);}

Жизнь - игра на ациклическом графе, а свобода - позиция, для которой есть >1 стратегии выигрыша.

Задачка для программистов

№ 22

Дата : 14-08-05, Вск, 02:45:21

Нее, рубяты

с лишними битами и умножениями не пойдёт. Бо тогда можно побитно разбить один разрешённый параметр хоть на целых три параметра. Что позволит вообще выкинуть вспомогательную функцию - с тремя параметрами тривиально решается безо всяких вспомогательных функций (например, параметры: cur_pos_in_line, cur_line_len, max_line_len). Так неинтересно, ибо накладывает ограничение на максимальное значение N.
Скажем так.. функция УиМа не сработает при вызове draw (MAX_INT).

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

Задачка для программистов

№ 23

Дата : 14-08-05, Вск, 02:47:06

А вот это куда интереснее

Надо проверить...
До двойной рекурсии не додумался

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

Задачка для программистов

№ 24

yxo

Дата : 14-08-05, Вск, 02:51:58

Грызь,

а как ты предполагаешь сохранять state в той же переменной, которую ты изменяешь ?

УиМ

Ясно, что твой один бит рулит ! Просто я привел пример формализации вопроса: клиент программы будет знать, что может использовать n бит максимум и получить искомый результат. В посте #13, этого не указанно. Ясно, что твоё решение завалится на underflow для определенных N.

Грызь ? А где твои предложения ?

...и днем и ночью

учёный всё ходит по цепи кругом...

Задачка для программистов

№ 25

Дата : 14-08-05, Вск, 02:57:34

Моих предложений нет

Потому что те, что были - совпадают с теми, что тут написали и были забракованы.
В частности - с умножением на два (один в один) и с глобальными переменными.
А идеального решения не придумал. Тупой

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

Задачка для программистов

№ 26

yxo

Дата : 14-08-05, Вск, 03:14:43

УиМ -- гардюсь ! Молодец.
БГ -- ну шо ? Цветочки ?

...и днем и ночью

учёный всё ходит по цепи кругом...

Задачка для программистов

№ 27