IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Числа. Точки на плоскости., N точек на плоскости, перестановки N чис
zetsokol
сообщение 28.11.2005 1:43
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 17
Пол: Мужской
Реальное имя: Александр

Репутация: -  0  +


Вот дали задачи на контрольную. Помогите кто чем может. blink.gif

1. N точек на плоскости заданы своими координатами. Найти порядок, в котором можно соединить эти точки, чтобы получился N-угольник (т.е. не было бы пересечений сторон).

2.Построить алгоритм, выдающий без повторений все перестановки N чисел.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов(1 - 13)
Altair
сообщение 28.11.2005 2:04
Сообщение #2


Ищущий истину
******

Группа: Модераторы
Сообщений: 4 824
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


Цитата
1. N точек на плоскости заданы своими координатами. Найти порядок, в котором можно соединить эти точки, чтобы получился N-угольник (т.е. не было бы пересечений сторон).


wink.gif
Представим множество точек на плоскости.
Прикрепленное изображение
Теперь проведем триангуляцию
Прикрепленное изображение
После этого у нас получилось не что иное как связанный граф.
Создаем для него матрицу смежности например (при этом запоминая, номера вершин какой точке соотвествуют).
После получаем задачу Эйлерова пути в чистом виде:
поиск цепи в графе, которая содержит все вершины и ребра в 1 экземпляре.

FAQ- >Эйлеров цикл в графе.


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Altair
сообщение 28.11.2005 2:08
Сообщение #3


Ищущий истину
******

Группа: Модераторы
Сообщений: 4 824
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


2. генерация всех перестановок элементов
отуда:
{ программа генерации перестановок N элементного 
множества в лексикографическом порядке }

Program perms;
var i,j,h,n,k:integer;
a:array[0..100] of integer; { массив для хранения перестановки }

{процедура вывода полученной перестановки}
procedure output;
var i:integer;
begin
writeln;
for i:=1 to n do write(a[i],' ');
end;

begin
readln(n); { ввод кол-ва элементов перестановки }
fillchar(a,sizeof(a),0); { инициализация массива }

{ ввод элементов начальной перестановки }
for i:=1 to n do a[i]:=i;

repeat
output; { ввод текущей перестановки }
i:=n;
while a[i-1]>a[i] do dec(i); { поиск скачка }
j:=i-1;
h:=a[j];
while a[i+1]>h do inc(i); { поиск первого меньшего элемента }
a[j]:=a[i]; a[i]:=h;
i:=j+1; k:=n;
while i<k do begin { перестановка ”хвоста” }
h:=a[i]; a[i]:=a[k]; a[k]:=h;
inc(i); dec(k)
end
until j=0; {}
end.



--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
zetsokol
сообщение 28.11.2005 2:16
Сообщение #4


Новичок
*

Группа: Пользователи
Сообщений: 17
Пол: Мужской
Реальное имя: Александр

Репутация: -  0  +


Огромное спасибо good.gif и не спицца тебе в такую пору. Только можно 1 задачу расписать полностью как и вторую и вот еще пару задач. Заранее БЛАГОДАРЕН.


3. В заданной строке определите количество слов, начинающихся и заканчивающихся на одну и ту же букву.

4. Натуральное число N>1 представить в виде суммы натуральных чисел так, чтобы произведение этих слагаемых было максимально.

Сообщение отредактировано: zetsokol - 28.11.2005 2:23
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Altair
сообщение 28.11.2005 2:41
Сообщение #5


Ищущий истину
******

Группа: Модераторы
Сообщений: 4 824
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


Цитата
и не спицца тебе в такую пору

чувства не дают...
Цитата
Только можно 1 задачу расписать полностью

Согласен, интересная задача... только утром smile.gif

Цитата
3. В заданной строке определите количество слов, начинающихся и заканчивающихся на одну и ту же букву.

function SepWord(s:string):integer;
const
r:set of char = [chr(0)..chr(255)]-['A'..'Z','a'..'z','1'..'9','0'];
var
i:integer; SL:boolean; ss:string;
pl:integer;
begin
sl:=false; ss:='' ; i:=1; pl:=0;
while i<=length(s) do begin
if ((not(s[i] in r)) and (sl=false)) then sl:=true;
if (not(s[i] in r)) and (sl=true) then ss:=ss+s[i];
if ((s[i] in r)or(i=length(s))) and (sl=true) then
begin
if ss[1]=ss[length(ss)] then inc(pl);
ss:=''; sl:=false;
end;
inc(i)
end;
SepWord:=pl;
end;

var
pl:integer;
s:String;
begin
writeln('Enter string....');
readln(s);
writeln('word count=',sepword(s));
readln;
end.


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
virt
сообщение 28.11.2005 9:12
Сообщение #6


Знаток
****

Группа: Пользователи
Сообщений: 419
Пол: Мужской

Репутация: -  6  +


вариант решения первой задачи ::
Цитата
1.строим выпуклую оболочку
2.добавляем оставшиеся вершины
а.условно разделяем множество на 2 половины по координате у
у нас будут 2 крайние точки(или отрезки)
б.берем точку P не принадлежащую оболочке ,если она в верхней половине то в верней части контура ищем отрезок из контура такой ,что x
координата точки лежит между его концами (P1 и P2). Удаляем ребро (P1,P2) и добавляем ребра (P1,P) и (P,P2). Мы добавили точку ,контур остался допустимым. Аналогично если точка находится в нижней половине.

Повторяем для всех не включенных в контур точек.


Эскизы прикрепленных изображений
Прикрепленное изображение

--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
zetsokol
сообщение 2.12.2005 17:08
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 17
Пол: Мужской
Реальное имя: Александр

Репутация: -  0  +


Altair огромное спасибо smile.gif


Virt или Altair помогите пожалуйсто с 4 задачей и вот с этой:


5.Сосчитать количество единиц в двоичной записи числа i.
вот некоторые соображения:

{poschitac edenicy}

program Edenicy;
var n,i,c,chislo,j:integer;

begin

readln(chislo);

n:=0;

for i:=1 to chislo do

begin
j:=i; c:=0;
while j<>0 do begin
if j mod 10 = 1 then inc©;
j:=j div 10;
end;
if c>=2 then inc(n);

end;

writeln(n);
readln;
end.


И если моно полный код задачи 1. Заранее СПАСИБО! Просто сроки поджимают

Сообщение отредактировано: volvo - 5.11.2006 21:37
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 2.12.2005 17:14
Сообщение #8


Гость






Цитата
Сосчитать количество единиц в двоичной записи числа

Я бы делал так:
var
X, i, n: Integer;
begin
Readln(X);

n := 0;
for i := 0 to 15 Do
if (($0001 shl i) and X) <> 0 then inc(n);

writeln(n);
end.


Решение задачи №4 есть здесь: http://algolist.manual.ru/olimp/ar_sol.php#a23
 К началу страницы 
+ Ответить 
zetsokol
сообщение 6.12.2005 10:20
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 17
Пол: Мужской
Реальное имя: Александр

Репутация: -  0  +


Распишите (Код программы) Pleese 4 и 1 задачи ну очень нуно уже скоро здаваться rolleyes.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 6.12.2005 10:31
Сообщение #10


Гость






zetsokol, ты что, сам думать совсем не хочешь? dry.gif
Вот четвертая:
var
X, p, n: Integer;
begin
Readln(X);

n := 0; p := 1;
while X > 3 do begin
inc(n); dec(X, 2);
end;

if X = 3 then begin
write(' 3'); p := 3;
end
else inc(n);

while n > 3 do begin
write(' 3 3'); dec(n, 3);
p := p * 9;
end;

while n > 0 do begin
write(' 2'); dec(n);
p := p * 2;
end;

writeln;
writeln('Произведение = ', p);
end.

Первая - нудная очень...

P.S. Не делай из темы свалку с несколькими вопросами !!!
 К началу страницы 
+ Ответить 
zetsokol
сообщение 6.12.2005 16:21
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 17
Пол: Мужской
Реальное имя: Александр

Репутация: -  0  +


Да просто я на VFoxPro работаю и времени нету все работа работа. Но за это огромное спасибо выручили меня smile.gif good.gif. Тока распишите(Код программы) пожалуйста 1 задачу и я отстану от ВАС. Спасибо!!!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
zetsokol
сообщение 9.12.2005 10:05
Сообщение #12


Новичок
*

Группа: Пользователи
Сообщений: 17
Пол: Мужской
Реальное имя: Александр

Репутация: -  0  +


Кто-нибудь помогите с первой задачей горю blink.gif mega_chok.gif smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 9.12.2005 15:54
Сообщение #13


Гость






Цитата
помогите с первой задачей

Ну, например, так:
Прикрепленный файл  polygon.pas ( 3.94 килобайт ) Кол-во скачиваний: 458


Тестировалось на следующих координатах:
Цитата(Console)
6 точек
3 2
6 4
8 5
12 3
10 6
5 8


Отдельное спасибо Romtek-у за процедуру построения выпуклой оболочки... blum.gif
 К началу страницы 
+ Ответить 
zetsokol
сообщение 18.12.2005 18:24
Сообщение #14


Новичок
*

Группа: Пользователи
Сообщений: 17
Пол: Мужской
Реальное имя: Александр

Репутация: -  0  +


Огромное тебе спасибо VOLVO applause.gif !thanks.gif !thanks.gif !thanks.gif respect2.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия 18.07.2025 10:04
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"