найти родственников

Задано конечное множество имен жителей некоего города,
причем для каждого из жителей перечислены имена его детей.
Жители X и Y называются родственниками ,если

a) либо X - ребенок Y
b) либо Y - ребенок X
c) либо существует некий Z такой, что X - родственник Z, а Z - родственник Y.

Перечислить все пары жителей города,которые являются родственниками.



Задача, как по мне, выше среднего уровня.

Первая проблема которая перед нами стоит - это как задать начальные данные.
Я долго думал на эту тему и пришел к выводу, что пользователю проще работать
с именами, чем с индексами соотв. имени. Поэтому я не пошел стандартным путём
(  а это задание вектора имен, потом задание вектора векоторов + вектор булевых переменных для раскраски... - муть зеленая)

Я использовал наборы из STL, т.е std::set

Для описания связи я использовал std::pair

Задав таким образом пары мы перезходим к следующей проблеме - нужно получить список уникальных имен, т.е. получить набор всех жителей. С этим отлично справился контейнер std::set.

Теперь нам нужно оценить каждого с каждым на предмет родства, это делать удобнее с std:vector - поэтому мы перегоняем данные из set в vector

Ну и самое главное - определение родства. Используем рекурсию для обхода дерева (направленный граф) для получения родственников для заданного человека, а потом ищем в нем того с чем определяем родство....


Полное решение будет стоит 250WMR. Обращайтесь.

как поменять элементы массива местами c

как поменять элементы массива местами (Си)

самый простой способ для понимания это представить себе переменную в виде стакана с водой

итого мы имеем 2 стака с жидкостями которые нужно поменять местами (содержимое стакана)

как бы вы сделали это в реальной жизни? так же и в программе! - посредством третьего стакана!


int a = 10;
int b = 20;
int temp; //наш третий стакан - посредник

temp = a; //перелили в третий стакан содержимое первого
a = b; //первый у нас освободился? заполняем его содержимым второго
b = temp; //второй освободился? заполняем его содержимым третьего (а там что?)

вот и поменялись...

javascript нахождение суммы цифр числа

javascript нахождение суммы цифр числа

<script>
var n = prompt ("number?", "1234")
var s = 0

while (n > 0)
{
 s += n % 10
 n = Math.floor(n/10)
}

alert("summa: " + s)
</script>

нерешенные еще проблемы

• распаковка rar файлов с русскими именами файлами в ubuntu 10.04

количество счастливых билетов

Кто возьмет билетов пачку, тот получит водокачку!

Нужно посчитать и вывести на экран количество "счастливых билетов"(к примеру: 111201, 333009 и так далее)

Примечание :

Счастливый билетик имеет вид XXXXXX.

var
    a,b,c,d,e,f: integer;
    g: double;
begin
    g:=0;
    for a:=0 to 9 do
    for b:=0 to 9 do
    for c:=0 to 9 do
    for d:=0 to 9 do
    for e:=0 to 9 do
    for f:=0 to 9 do
    if a+b+c=d+e+f then g:=g+1;
    writeln(g);
end.

PS: обычно я решаю сам, а этот пример подсмотрел - уж очень мне понравилась простота решения, единственное что я добавил - это g - переменная типа double, т.к. результат получается больше чем может представлять пременная типа int, ну и в оригинале было inc - пришлось сдеать g=g+1, ибо inc только для целочисленной математики, еще бы полагалось выводить знаки только до запятой (число то все равно целое), но это уже сами кому надо...

вывести матрицу из файла с++

вывести матрицу из файла с++

часто встречаю подобные задачи, вот один из способов реализации

отмечу только, что раз мы считываем матрицу из файла - то мы заранее
не знаем ее размер, а раз так - то память под неё мы выделяем динамически
с помощью оператора new (не забываем освобождать после использования)

и нужно придумать в каком виде хранить матрицу

создадим текстовый файл matrix.txt
с таким содержанием

2 3
1 2 3
4 5 6

в нем первая строка содержит два числа,
первое - количество строк матрицы, второе кол-во столбцов

#include <stdio.h>

int main(int argc, char * argv[])
{
 int n = 0;
 int m = 0;

 int **a;

 //открываем файл
 FILE * fp = fopen("matrix.txt", "r");
 if (fp)
 {
  //читаем количество строк и столбцов
  fscanf(fp, "%d %d", &n, &m);

  //выделяем место
  *a = new int(n);
  for (int i = 0; i < n; i++) a[i] = new int(m);

  //считываем данные из файла в матрицу
  for (int i = 0; i < n; i++)
  {
   for (int j = 0; j < m; j++)
   {
    fscanf(fp, "%d", &a[i][j]);
   }
  }
  
  //закрываем файл
  fclose(fp);
 }

 //печать матрицы
 for (int i = 0; i < n; i++)
 {
  for (int j = 0; j < m; j++)
  {
   printf("%d ", a[i][j]);
  }

  printf("\n");
 }

 //освобождение памяти
 for (int i = 0; i < n; i++) delete a[i];
 delete *a;


 return 0;
}

и вот вывод программы

1 2 3
4 5 6

перевод чисел из двоичной системы в текст

/* перевод чисел из двоичной системы в текст */

#include <stdio.h>

void main()
{
 int n = 1234;
 int i = 0;
 int m[32];

 printf("10: %d\n", n);

 while (n > 0)
 {
  m[i++] = n & 1;
  n = n >> 1;
 }

 printf(" 2: ");

 for (; i > 0; i--)
 {
  printf("%d", m[i-1]);
 }

 printf("\n");
}

массив состоит из 20 целых положительных и отрицательных чисел. выведите на экран сначала отрицательные, а затем положительные числа.

/* массив состоит из 20 целых положительных и отрицательных чисел.
 выведите на экран сначала отрицательные,
 а затем положительные числа. */

#include <stdio.h>

void main()
{
 int m[] = {1, -2, 3, 4, 5, 6, 7, 8, -9, 10, 11, -12, 13, 14, -15, 16, 17, -18, 19, 20};
 int i;

 printf("отрицательные: ");
 for (i = 0; i < 20; i++)
  if (m[i] < 0)
   printf("%d ", m[i]);

 printf("\n");


 printf("положительные: ");
 for (i = 0; i < 20; i++)
  if (m[i] > 0)
   printf("%d ", m[i]);

 printf("\n");
}

определить радиус и координаты центра окружности проходящей через заданные три точки

в процессе...

найти сумму цифр в числе используя рекурсивную подпрограмму

для простоты будем считать что числа только натуральные

function fun(x:integer; summa: integer) : integer;
var
   d, m: integer;
begin
   m := x mod 10;
   d := x div 10;
   if x > 0
   then fun := fun(d, summa + m)
   else fun := summa + m;
end;

begin
   writeln('cумма цифр = ', fun(1234, 0));
end.

Нахождение корня функции.

Здесь описан метод половинного деления (дитохомии?). Суть проста. Есть функция f(x), есть интервал [a,b], есть условие, что на концах промежутка функция имеет разный знак: f(a)*f(b)<0. Требуется найти с заданной точностью eps корень этой функции. Поступаем так: выбираем середину отрезка [a,b]. Если в середине функция имеет тот же знак что и слева, то принимаем середину за новую левую границу, в противном случае - за правую. Повторяем до тех пор, пока отрезок не станет меньше eps. В данном примере в качестве функции берем синус, а отрезок - [3,4]. Таким образом мы должны найти число пи.

function f(x:real):real;
  begin
  f:=sin(x);
  end;
const MaxSteps=200;
var a0,b0,a,b,eps,fa,fb,t,ft:real;
    step,sa,sb:integer;
begin
writeln('Нахождение корней функции методом половинного деления:');
a0:=3; {writeln(' Input a0: ');readln(a0);}
b0:=4; {writeln(' Input b0: ');readln(b0);}
eps:=0.0000001; {writeln(' Input eps: ');readln(eps);}
fa:=f(a0); fb:=f(b0);
if (fa*fb>0) then
  begin
  writeln(' На заданном промежутке корней нет.');
  halt;
  end;
a:=a0; b:=b0;
step:=0; t:=a; ft:=fa;
while (abs(b-a)>eps) and (step<MaxSteps) do
  begin
  inc(step);
  t:=(a+b)/2;
  ft:=f(t);
  if (fa*ft>0) then
    begin
    fa:=ft;
    a:=t;
    end
  else
    b:=t;
  writeln('step:',step:4,' t=',t,' f(t)=',ft);
  end;
if (step>MaxSteps)
  then writeln('Отсутствие сходимости. Уточните промежуток.')
  else writeln('Найден корень с заданной точностью.');
end.

нахождения корней уравнения методом половинного деления

PROGRAM KORNI;
VAR A,B,PREC:REAL;
FUNCTION F(X:REAL):REAL;
BEGIN
 F:=X*X-3*X+2
END;
FUNCTION KORENJ(A,B,PREC:REAL):REAL;
VAR X,Y,Z:REAL;
BEGIN
 IF ABS(A-B)<PREC THEN KORENJ:=(A+B)/2
   ELSE BEGIN
   X:=F(A);
   Y:=F((A+B)/2);
   Z:=F(B);
   IF X*Y<0 THEN KORENJ:=KORENJ(A,(A+B)/2,PREC)
            ELSE KORENJ:=KORENJ((A+B)/2,B,PREC)
   END
END;
BEGIN
 READLN (A,B,PREC);
 WRITELN ('X=',KORENJ(A,B,PREC))
END.

определитель матрицы

и снова определитель матрицы

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

const int n = 4;

void print(int**, int);
void clear(int**, int**, int, int, int);
long Determinant(int**, int);

void main()
{
 time_t t;
 srand(time(&t));

 int** a = new int*[n];
 for (int i = 0; i < n; i++) a[i] = new int[n];


 for (int i = 0; i < n; i++)
 {
  for (int j = 0; j < n; j ++)
  {
   a[i][j] = rand() % 10;
  }
 }

 print(a, n);

 long dt = Determinant(a, n);
 printf("\nDeterminant = %d\n", dt);

 for (int i = 0; i < n; i++) delete[] a[i];
 delete[] a;
}

void print(int** a, int n)
{
 for (int i = 0; i < n; i++)
 {
  for (int j = 0; j < n; j++)
  {
   printf("%d\t", a[i][j]);
  }

  printf("\n");
 }
}

void clear(int** a, int** b, int m, int i, int j)
{
 int di = 0;
 int dj;

 for (int ki = 0; ki < m - 1; ki++)
 {
  if (ki == i)
   di = 1;

  dj = 0;
  for (int kj = 0; kj < m - 1; kj++)
  {
   if (kj == j)
    dj = 1;

   b[ki][kj] = a[ki + di][kj + dj];
  }
 }
}

long Determinant(int** a, int n)
{
 if (n == 1)
  return a[0][0];

 if (n == 2)
  return a[0][0] * a[1][1] - a[0][1] * a[1][0];

 int** b = new int*[n];
 for (int i = 0; i < n; i++) b[i] = new int[n];

 int d = 0;
 int k = 1;
   
 for (int i = 0; i < n; i++)
 {
  clear(a, b, n, i, 0);
  d += k * a[i][0] * Determinant(b, n - 1);
  k--;
 }

 for (int i = 0; i < n; i++) delete[] b[i];
 delete[] b;

 return d;
}

борьба с банерами от порно-информермеров

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

Наши Касперские и др. не спят и уже придумали генераторы кодов для снятия блокировок.

Здесь представлены генераторы кодов от разных производителей:

• от Касперского
• от д. Веба
• от Вирусинфо

полезные скрипты для bash

замена переводов строк на запятую
$ awk '{printf $0","}' input.txt > output.txt

размер директории (заметьте - новый формат в системе CИ)
$ du --si

среднее арифметическое введенных чисел

Создайте сценарий, который будет выводить среднее арифметиское из неограниченного числа, введенных пользователем значений. Ввод будет продолжаться до тех пор пока не будет введен 0. После ввода 0 программа будет выводить на экран все введенные числа и подститанное значение средного арифметического из этих чисел.

var summa = 0;
var n = 0;
while (true)
{
 var x = prompt('input x:');
 if (x == 0)
  break;

 summa += parseInt(x);
 document.write(x);
 document.write("<br>");
 n++;
}

if (n != 0)
{
 document.write("----<br>avg=");
 document.write(summa/n);
}

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