Задачи

Помогите решить задачу. Кому-то она уже знакома, кто-то ее даже решил... Заранее спасибо.

Иван Иванович Иванов пригласил на свой день рождения много гостей. Он написал на карточках фамилии всех гостей и разложил эти карточки на столе, полагая, что каждый гость сядет там, где обнаружит карточку со своей фамилией. Однако гости не обратили внимания на карточки и сели за стол в произвольном порядке. При этом Иван Иванович с удивлением обнаружил, что ни один гость не сел на предназначенное ему место, и задумался: а сколькими способами можно рассадить гостей так, чтобы ни один из них не сидел там, где лежала карточка с его фамилией? Помогите Ивану Ивановичу вычислить это число.

Ввод

Число гостей, не превышающее 100.

Вывод

Число способов.

Например,

  1. Ввод        Вывод
  2. 10      1334961

Забыла самое главное сказать.

Забыла самое главное сказать. Желательно, на Pascal. Smile

для решения этой задачи

для решения этой задачи потребуется знания по комбинаторике! нам нужна формула перестановки без повторений, вот так она выглядит P(n)=n!

теперь дело за программой...

program komb;
var n,i:integer;
m:real;
begin
writeln('vvedite chislo gostey');
readln(n);
m:=1;
for i:=1 to n do
begin
m:=m*i;
end;
Writeln('chislo kombinaciy=',m:0:0);
readln;
end.

только там баг

n! - это число всех способов

n! - это число всех способов посадить гостей за стол. И туда попадает случай, когда гость сядет на свое место с табличкой.

На основе предыдущей

На основе предыдущей программы:

{$N+}
Program a;
type real=extended;
var n, i:integer; m:real;
begin
writeln ('number of guests:');
readln (n);
m:=1;
for i:=1 to n do m:=m*i;
writeln (m:0:0);
readln;
end.

Баг устранен, алгоритм поправьте, а то я off...

P(n)=n! эта формула для

P(n)=n! эта формула для нахождения количества перестановок без повторений

баг устранен но не до конца,

баг устранен но не до конца, можно рассадить только 17 человек((

С чего ты взял, что только

С чего ты взял, что только 17? )) Рассадить можно хоть 1000.

ну да....и какой тип в

ну да....и какой тип в паскале покажет 1000! ?

если 170!=7.25741562 × 10^306

А в чем, собственно, вообще

А в чем, собственно, вообще баг был и есть? оО.

ну то что паскаль не может

ну то что паскаль не может дощитать до "числа гостей не превышающее 100"

интероесто а можноли исользовать  int64  в паскале?

Баг в том,что не правильно

Баг в том,что не правильно считает Smile. При вводе: 10 должен выводить: 1334961 , а выводит: 3628800

что то я не

что то я не пойму.....10!=3628800

Больше троих не приглашать!

Да разберитесь вы пока с 2-3-мя гостями, хлебосольные мои!

Дело в том, что формула n! не

Дело в том, что формула n! не подходит для данной задачи. Пусть у нас двое гостей. И сколькими способами мы их можем рассадить, так чтобы не сели на свое место с табличкой??? Ответ, конечно же одним способом! (Посадим 1-ого на место 2-ого, а 2-ого на место 1-ого). А по формуле получается: 2!=1*2=2, что не верно!

да, конечно верный ответ n-1

да, конечно верный ответ n-1  способ

А программа при вводе 2

А программа при вводе 2 выдает тоже 2 Laughing

 

Почему не может досчитать?

Почему не может досчитать? Говори конкретней. У меня выдает ответ на запрос и 100 гостей, и 500 гостей, как я понимаю, раньше, твоя программа, Адам, не выдавала результат на более чем 33 гостя, сейчас все поправлено, я думал, что ты имеешь ввиду, что баг именно в этом. :?
А то, что алгоритм не верный - это да.

Не досчитает, потому что в

Не досчитает, потому что в паскале нету типа куда бы поместился 100!, из-за это, все что не попадает в диапазон типа "обрезается" и подсчет становиться не правильной. Чтобы этого не происходила используют так называемую "длинную арифметику".

фуф, ну я поняла почему не

фуф, ну я поняла почему не n!. Но почему тогда для n-1 не работает? Эта задача с контестера. Так что будем надеяться, что в выводе в задаче нет ошибок

там не n-1!(факториал)   а

там не n-1!(факториал)   а просто n-1

А, ну это да. Наглядного

А, ну это да. Наглядного вывода после 33! уже не будет. ^^))

write('vvedite chislo gostey

write('vvedite chislo gostey ');
readln(n);
nf:=1;
for i:=1 to n-1 do begin
nf:=nf*i;
end;
Writeln('chislo kombinaciy=', nf);

Не так?

Что-то мне подсказывает, что

Что-то мне подсказывает, что совсем не так. Undecided

Ну да, ответ ведь неверный. Я

Ну да, ответ ведь неверный. Я говорю о 10-ти. Но в чем же ошибка?

Может, нужно делать n-1(+) не

Может, нужно делать n-1(+) не только для гостей, но и для стульев на которые они садятся?

Я думала, что это и было для

Я думала, что это и было для стульев. Surprised А рассадить ведь нужно n гостей

А Вы что думаете?

А Вы что думаете? Smile

Программка

program sp; {$APPTYPE CONSOLE}
uses SysUtils;
var i,a,b,n,sposobi,d:longword;
begin
write('введите число гостей:');
readln(n);
if (n=0) or (n=1) then write('число способов:0');
if n=2 then write('число способов:1');
if n=3 then write('число способов:2');
a:=3;
sposobi:=2;
if n>3 then
for i := 4 to n do begin
d:=i; {может быть переменная d лишняя но в For i нельзя менять...}
b:=a*(d-1);
a:=b+sposobi;
sposobi:=b;

end;
if n>3 then write('число способов:',sposobi);
readln;
{ в delphi всё работает ЧЁТКО ! ! ! а в PASCAL'E следует изменить в var'е тип или же реализовать вывод такого максимального числа способов )
тут ещё можно убрать if-ы поставит case но мне так приятнее :)))

)))}
// если найдёте БАГ в алгоритме СООБЩИТЕ ! ! ! ! хотя врядли найдёте ;)
end.

Все правильно, не спорю.

Все правильно, не спорю. Можешь объяснить, на чем основано твое решение? Может быть ты использовал какую-то формулу? Можешь пояснить? И, наверное, d все-таки можно было не использовать, потому что в этом действии ты меняешь b, но d и следовательно i не меняются.

пояснение...

Ах ну да самое главное забыл написать... я с телефона обычно захожу, а с телефона оставлять коментарии не возможно... теперь на счёт задачи, ну если по формуле она будет выглядить так:
P(n)=A*(n-1)+B , где B - это число комбинаций от (n-1) гостя без повторений, а A - это тоже число комбинаций, но добавляется условие, что один из гостей будет повторятся => всегда вып-ся условие A>B,
я исходил из того, что n! - это как уже сказанно число всего комбинаций с повторениями => можно найти число комбинаций без повторенний одного из гостей, и т. д. таким образом можно исключить то число способов с повторениями ! ! ! которое так важно. оживим выше сказанное на примере:
рассмотрим вид:
( N : X --- S ),
где N- число гостей,
Х- число гостей которое может сидеть и на своём месте
S - Число комбинаций.

далее...

пусть число гостей N=2 , число которое может сидеть и на своём месте X=2 => S=2!=2
при N=2 , X=1 => S=1
N=2 , X=0 => S=1
N=3 , X=3 => S=3!=6
N=3 , X=2 => S=4
N=3 , X=1 => S=3 * //ниже есть пояснение...
N=3 , X=0 => S=2 **// это то что нам надо(число способов без повторений

N=4 , X=4 => S=4!=24
. . .
N=4 , X=1 => (S=11) *
N=4 , X=0 => (S=9) **

N=5 , X=5 => S=5!=120
. . .
N=5 , X=1 => S= (a *(5 - 1)+sposobi)
N=5 , X=0 => S=a* (5 - 1) **, где a=11
и т.д.

* - это есть в программе как переменная - a
**- sposobi

А по теории вероятности мы будем проходить всё это??? :)

Наташа на счёт d да, не правильно выразился ... вот попробуй без d , программа будет выводить что то необыкновенное))) у тебя не знаю, у меня так было!

Спасибо за помощь

Спасибо за помощь

Наташа, как ты так быстро

Наташа, как ты так быстро решаешь Задачи???

Ээээ... В смысле?

Ээээ... В смысле?

в прямом.....! как я не

в прямом.....!Smile как я не посмотрю, только выложили новую  прогу, ты уже её решьла!!! Как у тебя так получается? ты ходила на какие-то курсы???Smile

Саша, какие курсы!!! Это

Саша, какие курсы!!! Это особый склад ума...называется математический!!! Все дано от природы)))

Кстати Наташа, на счёт твоей

Кстати Наташа, на счёт твоей ссылки на книгу...тут формат .djvu Впрос, через что его откравыть?Embarassed

скачать можно здесь

скачать можно здесь

http://windjview.sourceforge.net/ru/

у меня вопрос, там точно при 10 гостях 1334961 ?

P S

попробуй контро-пример придумать)))

Так я даже если и не делаю

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

Задания на лаб.

Вот несколько задач на рекурсию. Оцениваю первые те, которые не сочту по существу одинаковыми.
"Засветиться" прошу всех присутствующих.

Задача1. Дано натуральное число. Напечатать его десятичные цифры в обратном порядке.
Задача2. Дано натуральное число. Перевести его (напечатать) в 8-ричную с.с.
Задача3. Дано натуральное число. Проверить, явлется ли оно палиндромом.
Это для начала. В задачах массивы не использовать.

Задача №2

Валерий Шахамболетович, я сейчас попробую без цикла.

program z2;
var oct,c:string;
dec,i:integer;
begin
write('DEC=');readln(dec);
oct:='';
while dec>0 do
begin
i:=dec mod 8;
dec:=dec div 8;
str(i, c);
oct:=c+oct;
end;
writeln('OCT=',oct);
readln;
end.

Да, но где рекурсия?

Да, но где рекурсия?

Задача №1

program Zadacha1;

{$APPTYPE CONSOLE}

uses
SysUtils;
var n:word;
procedure G(n:word);
begin
if n<10 then write (n)
else begin write(n mod 10); G(n div 10);
end;
end;

begin
read (n);
g(n); readln;

end.

Казаков +. А вот флуд ни к

Казаков +. А вот флуд ни к чему!

Zadacha1

program z1;
{$APPTYPE CONSOLE}
var n:word;
procedure sis(n:word);
begin
if n<10 then write (n)
else
begin
write(n mod 10);
sis(n div 10);
end;
end;
begin
read (n);
sis(n);
readln;
end.

Задача №3

program Zadacha3;
{$APPTYPE CONSOLE}
uses
SysUtils;
var a,n:word;
procedure G(n:word; var a:word);
begin
if n<10 then a:=a*10+n
else begin a:=(a*10)+(n mod 10); G(n div 10,a);
end;
end;
begin
read(n);
a:=0;
g(n,a);
if a=n then writeln('da')
else writeln('net');
readln;
end.
И прошу прощения за флуд.

Задача №1

program project1;

var a:integer;
function Des(a:integer): cardinal;
var c: integer;
begin
if a<10 then write (a)
else begin
c:=a mod 10;
write(c);
Des(a div 10);
end;
end;

begin
read (a);
Des(a);
readln;
readln;
end.

Задача №3

program Project3;
{$APPTYPE CONSOLE}
uses
SysUtils;
var a,n:word;
function Polindrom(n:word; var s:word): Integer;
begin
if n<10 then s:=s*10+n
else begin s:=(s*10)+(n mod 10); Polindrom(n div 10,s);
end;
end;
begin
read(n);
a:=0;
Polindrom(n,a);
if a=n then writeln('yes')
else writeln('no');
readln;
end.

Закрываем. Итог: Казаков 2,

Закрываем.
Итог: Казаков 2, Губжоков 1.

Лаб. ИС1.2

Условия почитайте выше. Все задачи делать рекурсией.

Задача1. Задан стринг. Проверить, представляет ли он собой палиндром.
Задача2. Заданы натуральные M и N. Не используя div и mod найти y= M mod N.
Задача3. Задано натуральное N. Определить, является ли оно целой степенью числа 2.