Числа. Точки на плоскости., N точек на плоскости, перестановки N чис Опции

[zetsokol]

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

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

2.Построить алгоритм, выдающий без повторений все перестановки N чисел.

[Altair]

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

Представим множество точек на плоскости.

Теперь проведем триангуляцию

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

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

[Altair]

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.

[zetsokol]

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


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

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

Сообщение отредактировано: zetsokol - 28.11.2005 6:23

[Altair]

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

чувства не дают...

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

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

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.

[virt]

вариант решения первой задачи ::

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

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

[zetsokol]

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


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 - 6.11.2006 1:37

[volvo]

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

Я бы делал так:

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]

Распишите (Код программы) Pleese 4 и 1 задачи ну очень нуно уже скоро здаваться

[volvo]

zetsokol, ты что, сам думать совсем не хочешь?
Вот четвертая:

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]

Да просто я на VFoxPro работаю и времени нету все работа работа. Но за это огромное спасибо выручили меня . Тока распишите(Код программы) пожалуйста 1 задачу и я отстану от ВАС. Спасибо!!!

[zetsokol]

Кто-нибудь помогите с первой задачей горю

[volvo]

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

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


Тестировалось на следующих координатах:

6 точек
3 2
6 4
8 5
12 3
10 6
5 8

Отдельное спасибо Romtek-у за процедуру построения выпуклой оболочки...

[zetsokol]

Огромное тебе спасибо VOLVO