Вычислить остаток целочисленного деления

@syc07 · Регистрация: 17.03.2010

Студворк — интернет-сервис помощи студентам

Раз уж тема по рекурсии, влезу ка я со своим вопросом.
как написать оную для возвращения целого остатка при целочисленном делении, используя только sub1

@Catstail · 24.05.2012, 16:42

Вот решение с add1:

Lisp
1
2
3
4
5
6
7
(defun dif (x y) (cond ((= x y) 0) ;; вычитание x-y
                       ((> x y) (add1 (dif x (add1 y))))
                       (t (minus (dif y x)))))
 
(defun rem (x y) (cond ((= x y) 0) ;; остаток от деления x на y (x,y > 0)
                       ((< (dif x y) y) (dif x y))
                       (t (rem (dif x y) y))))

Добавлено через 1 час 13 минут
Вот решение с add1 и sub1:

Lisp
1
2
3
4
5
6
7
(defun dif (x y) (cond ((= x y) 0)
                       ((> x y) (add1 (dif x (add1 y))))
                       (t (sub1 (dif x (sub1 y))))))
 
(defun rem (x y) (cond ((= x y) 0)
                       ((< (dif x y) y) (dif x y))
                       (t (rem (dif x y) y))))

@bokunopico · 24.05.2012, 16:50

Только ~~sub1~~ 1-, только хардкор:

Lisp
1
2
3
4
(defun f (a b &optional (n 0))
  (cond ((/= n 0) (f (1- a) b (1- n)))
        ((< a b) a)
        (t (f a b b))))

@syc07 · 25.05.2012, 15:14 **[ТС]**

Сообщение от bokunopico

Только ~~sub1~~ 1-, только хардкор:

Lisp
1
2
3
4
(defun f (a b &optional (n 0))
  (cond ((/= n 0) (f (1- a) b (1- n)))
        ((< a b) a)
        (t (f a b b))))

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

@Catstail · 25.05.2012, 15:35

Без OPTIONAL? Так ведь можно сделать параметр обязательным (убрать &optional) и обращаться вот так:

Lisp
1
(f a b 0)

Если не хочется так, можно ввести функцию-оболочку:

Lisp
1
(defun ff (a b) (f a b 0))

@syc07 · 25.05.2012, 16:36 **[ТС]**

Catstail, не могли бы вы по шагам проверить выполнение программы, т.е. программа так считает?
a=7 b=3.
1. все пропускаем, выполняется последнее условие n=b=3;
2. выполняется 1ое условие. a=6; b=3; n=2;
3 выполняется 1ое условие a=5; b=3; n=1;
4 выполняется 1ое условие a=4; b=3; n=0;
5. все пропускаем, выполняется последнее условие. n=3;
6. выполняется 1ое условие a=3; b=3; n=2;
7. выполняется 1ое условие a=2; b=3; n=1;
8. выполняется 1ое условие a=1; b=3; n=1;
9. выполняется второе (a<b?) условие a=1.

@Catstail · 25.05.2012, 17:03

Вот протокол трассировки (HomeLisp):

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(f 7 3)
 
Вход в функцию f Аргументы: 7 3
  Вход в функцию f Аргументы: 7 3 3
    Вход в функцию f Аргументы: 6 3 2
      Вход в функцию f Аргументы: 5 3 1
        Вход в функцию f Аргументы: 4 3 0
          Вход в функцию f Аргументы: 4 3 3
            Вход в функцию f Аргументы: 3 3 2
              Вход в функцию f Аргументы: 2 3 1
                Вход в функцию f Аргументы: 1 3 0
                Возврат из функции f Результат: 1
              Возврат из функции f Результат: 1
            Возврат из функции f Результат: 1
          Возврат из функции f Результат: 1
        Возврат из функции f Результат: 1
      Возврат из функции f Результат: 1
    Возврат из функции f Результат: 1
  Возврат из функции f Результат: 1
Возврат из функции f Результат: 1
 
==> 1

@syc07 · 27.05.2012, 21:27 **[ТС]**

Поставьте на пусть истинный еще с одной рекурсией, типа золотое сечение.
sqrt(1+sqrt(1+sqrt(1+sqrt(1+sqrt(1+sqrt( 1+.....))))))

Lisp
1
2
3
4
(defun ab (n)
  (cond ((/= n 0) (sqrt (1+ (ab))) (1- n))
        (t (ab n))
        ))

@Catstail · 28.05.2012, 07:55

Во второй строке ab вызвана без аргумента. Это ошибка.
А если n=0, то программа зациклится.

@syc07 · 28.05.2012, 21:05 **[ТС]**

Сообщение от Catstail

Во второй строке ab вызвана без аргумента. Это ошибка.
А если n=0, то программа зациклится.

Lisp
1
2
3
4
(defun ab (n)
  (cond ((/= n 0) (sqrt (1+ (ab (1- n)))))
        (t (ab n))
        ))

Lisp
1
2
3
4
5
6
7
8
9
10
     
(trace AB )
 
(AB 5)
Entering function AB with params (5)
 Entering function AB with params (4)
  Entering function AB with params (3)
   Entering function AB with params (2)
    Entering function AB with params (1)
     Entering function AB with params (0)

вроде не циклится, но самое главное - не возвращает параметр.

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

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(defun ab (n)
  (cond ((< n 2) 1)
        ((<> n 0) (sqr (add1 (ab(sub1 n)))))
        (t (ab n))
        ))
 
 
==> ab
 
(ab 4)
 
Вход в функцию ab Аргументы: 4
  Вход в функцию ab Аргументы: 3
    Вход в функцию ab Аргументы: 2
      Вход в функцию ab Аргументы: 1
      Возврат из функции ab Результат: 1
    Возврат из функции ab Результат: 1.4142135623731
  Возврат из функции ab Результат: 1.55377397403004
Возврат из функции ab Результат: 1.59805318247862
==> 1.59805318247862

все верно?

@Catstail · 29.05.2012, 07:52

Да, но строчка (t (ab n)) - лишняя! Смотри - без нее все работает так же:

Lisp
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
(defun ab (n)
  (cond ((< n 2) 1)
        ((<> n 0) (sqr (add1 (ab(sub1 n)))))
        ))
 
==> ab
 
(ab 4)
 
==> 1.59805318247862
 
(trace ab)
 
==> ab
 
(ab 4)
 
Вход в функцию ab Аргументы: 4
  Вход в функцию ab Аргументы: 3
    Вход в функцию ab Аргументы: 2
      Вход в функцию ab Аргументы: 1
      Возврат из функции ab Результат: 1
    Возврат из функции ab Результат: 1.4142135623731
  Возврат из функции ab Результат: 1.55377397403004
Возврат из функции ab Результат: 1.59805318247862
 
==> 1.59805318247862

Новые блоги и статьи Все статьи Все блоги /
Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .
Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .	Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .

@syc07 2 / 2 / 1 Регистрация: 17.03.2010 Сообщений: 23

	Вычислить остаток целочисленного деления 23.05.2012, 22:37. Показов 9276. Ответов 10 Метки нет (Все метки) Раз уж тема по рекурсии, влезу ка я со своим вопросом. как написать оную для возвращения целого остатка при целочисленном делении, используя только sub1 0

@syc07 2 / 2 / 1 Регистрация: 17.03.2010 Сообщений: 23
	25.05.2012, 16:36 [ТС]
	Catstail, не могли бы вы по шагам проверить выполнение программы, т.е. программа так считает? a=7 b=3. 1. все пропускаем, выполняется последнее условие n=b=3; 2. выполняется 1ое условие. a=6; b=3; n=2; 3 выполняется 1ое условие a=5; b=3; n=1; 4 выполняется 1ое условие a=4; b=3; n=0; 5. все пропускаем, выполняется последнее условие. n=3; 6. выполняется 1ое условие a=3; b=3; n=2; 7. выполняется 1ое условие a=2; b=3; n=1; 8. выполняется 1ое условие a=1; b=3; n=1; 9. выполняется второе (a<b?) условие a=1. 0

@Catstail Супер-модератор 38167 / 21102 / 4307 Регистрация: 12.02.2012 Сообщений: 34,690 Записей в блоге: 14
	28.05.2012, 07:55
	Во второй строке ab вызвана без аргумента. Это ошибка. А если n=0, то программа зациклится. 0