07.06.2020, 09:19 [+3 UTC]
в нашей команде: 4 600 чел. | участники онлайн: 1 (рекорд: 21)

:: РЕГИСТРАЦИЯ

задать вопрос

все разделы

правила

новости

участники

доска почёта

форум

блоги

поиск

статистика

наш журнал

наши встречи

наша галерея

отзывы о нас

поддержка

руководство

Версия системы:
7.89 (25.04.2020)
JS-v.1.45 | CSS-v.3.39

Общие новости:
13.04.2020, 00:02

Форум:
05.06.2020, 04:11

Последний вопрос:
06.06.2020, 21:42
Всего: 152584

Последний ответ:
07.06.2020, 07:20
Всего: 260260

Последняя рассылка:
07.06.2020, 05:15

Писем в очереди:
0

Мы в соцсетях:

Наша кнопка:

RFpro.ru - здесь вам помогут!

Отзывы о нас:
10.10.2009, 13:49 »
Искужина Светлана Юлаевна
Спасибо огромное Леониду! [вопрос № 172875, ответ № 255166]
07.05.2019, 19:23 »
svrvsvrv
Спасибо за полезную информацию! [вопрос № 195546, ответ № 278081]

РАЗДЕЛ • С / С++

Создание программ на языках C и C++.

[администратор рассылки: Андрей Кузнецов aka Dr_Andrew (Старший модератор)]

Лучшие эксперты в этом разделе

Коцюрбенко Алексей Владимирович
Статус: Старший модератор
Рейтинг: 1726
var
Статус: 7-й класс
Рейтинг: 719
Зенченко Константин Николаевич
Статус: Старший модератор
Рейтинг: 430

Перейти к консультации №:
 

Консультация онлайн # 145975
Раздел: • С / С++
Автор вопроса: Piotr-1
Отправлена: 04.10.2008, 15:36
Поступило ответов: 1

Здравствуйте, помогите пожалуста решить след. задачи и отладить или решить заново задачу в приложении:
4. Вроде всё правильно, но глючит. см. приложение.
5. Задана матрица A(n,m), упорядоченная по возрастанию построкам и столбцам, то есть
A(i,1)<=A(i,2)<=...<=A(i,m), для любого i
A(1,j)<=A(2,j)<=...<=A(n,j), для любого j
6. Даны 2 целочисл. таблицы A(10) и B(15). Разработать алгоритм и написать программу, которая проверяет,
являются ли эти таблицы похожими. 2 таблицы будем называть похожими, если совпадают множества чисел,
встречающихся в этих таблицах.
PS: все задачи на тему "Сложность и эффективность алгоритмов. Поиск и сортировка информации", нумеровка
как в списке задач.

Приложение:

Состояние: Консультация закрыта

Ответ # 231176 от Владимир (C4tnt)

Здравствуйте, Piotr-1!

4. Если у вас список монет сортированый - то ищите эталон двоичным или троичным поиском, более быстрый алгоритм довольно сложно придумать. А на несортированные списки быстрый поиск вообще не распространяется - ищите перебором.

5. Вопрос так и не задали...

6. Если таблицы не сортированы - берём первое число в B, удаляем из B все его вхождения, удаляем из A все его вхождения, если из А ничего удалено не было - значит списки не похожи. Если B пустой, а A - нет, значит списки не похожи.


Консультировал: Владимир (C4tnt)
Дата отправки: 04.10.2008, 20:24

Рейтинг ответа:

0

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

Мини-форум консультации № 145975
Denisss

# 1

= общий = | 05.10.2008, 17:52

Если я правильно понял пункт 4., то вот одно из возможных решений:

//Дан набор монет, и ещё одна монета (эталон). Есть ли в наборе монета, равная
//по весу эталону?

//Я так понимаю, может и неправильно ;), что в наборе все монеты одинаковые по весу, и если в нем
//присутствует эталон, то только один.

#include <iostream>  // cin, cout
#include <vector>    // vector<>
#include <algorithm> // copy(), find()
#include <iterator>  // istream_iterator<>, distance()
#include <conio.h>  // getch()

using namespace std;

typedef vector<int> IntV;

int main ()
{
    IntV c;
    int metalon;
    cout << "Enter weight of etalon\n"; cin >> metalon;

    cout << "Enter weight of coin or -1 to end\n";

    // тип unsigned взят специально,
    // когда пользователь введет отрицательное число
    // или любой символ, ввод прекратится
    copy(istream_iterator<unsigned>(cin), istream_iterator<unsigned>(),
        back_inserter(c));

    // Поиск этанола в массиве
    IntV::iterator etalon2(find(c.begin(), c.end(), metalon));

    // если найден
    if (etalon2 != c.end())
    {
        // ищем еще один
        if (find(etalon2+1, c.end(), metalon) == c.end())
            // найден только один
            cout << "Yes, there is the second etalon in the array at position " << distance(c.begin(), etalon2);
        else
            // найдено два
            cout << "There are more than two etalons in the array";
    }
    else
        // не найдено ни одного
        cout << "There is no more etalons in the array";
    cout << endl;

    getch();

    return 0;
}
deque был заменен на vector. deque - это двусторонние очереди, но в Вашем случае она используется как односторонняя очередь (используете только push_back()), а в качестве односторонней очереди (ИМХО) лучше использовать обычный вектор. Ну и для поиска, по-моему, лучше использовать стандартные алгоритмы (модуль <algorithm>), если не указано, что поиск нужно реализовать самостоятельно.

Владимир (C4tnt)

# 2

= общий = | 05.10.2008, 18:25

Странно smile Отправили бы как ответ, он бы хоть в рассылку попал...

неизвестный

# 3

= общий = | 07.10.2008, 12:37

5. Конец условия задачи (так торопился, что забыл дописать):
Найти элемент матрицы, равный заданному числу X и отпечатаь его индексы.
Напечатать "такого элемента нет", если такого элемента в массиве не окажется.
Х можно сравнивать не более, чем с N+M элементами матрицы.

4. (пояснение) Монеты взвешиваются на рычажных весах. Полный перебор не использовать.

Denisss

# 4

= общий = | 07.10.2008, 22:23

А нельзя ли, в таком случае, полностью задачу 4 сформулировать (как указано в задании). А то что-то до меня не доходит ее смысл.

неизвестный

# 5

= общий = | 08.10.2008, 22:23

Дан набор монет и ещё одна монета (назовём её эталоном). Есть ли в наборе монета, равная по весу эталону? Монеты взвешиваются на рычажных весах. Полный перебор не использовать.
//вот и всё условие задачи. Больше ничего не знаю

неизвестный

# 6

= общий = | 08.10.2008, 22:41

Кстати, решил 6 задачу:
#include <iostream>
#include <list>
#include <fstream>
using namespace std;

int main ()
{
const int n = 10, m = 15;
list<int> a(n), b(m);
list<int>::iterator i;
ifstream inp ("input.txt");
ofstream outp ("output.txt");
for (i = a.begin (); i != a.end (); ++i) inp >> *i;
for (i = b.begin (); i != b.end (); ++i) inp >> *i;
a.sort (); b.sort ();
a.unique (); b.unique ();
if (a.size () != b.size ()) outp << "Tables are not similar";
else {
for (i = a.begin (); i != a.end (); ++i) b.remove (*i);
if (b.size () == 0) outp << "Tables are similar";
else outp << "Tables are not similar";
};
return 0;
}

4 и 5 же задачи у меня никак не получается решить. Помогите, пожалуйста,
срочно решить их к вечеру пятницы...

неизвестный

# 7

= общий = | 10.10.2008, 22:01

пожалуйста, скажите почему в строке, помеченной коментарием, ошибка (Dev-C++4.9) ????!!!!!!
//Дан набор монет, и ещё одна монета (эталон). Есть ли в наборе монета, равная
//по весу эталону? монеты взвешиваются на рычажных весах. Полный перебор не использовать.
//Предположим, что в наборе все монеты одинаковые по весу, и если в нем
//присутствует эталон, то только один.
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int ves (int begin, int end, vector<int> c) {
int sum;
for ( ; begin <= end; begin++) sum += c[begin];
return sum;
};

bool reshenie (int l, int r, vector<int> c, int metalon) {
int m;
if ( (r-l)%2 == 1 ) {
if (metalon == c[r]) return true;
else r--;
};
m = (r-l)/2;
if ( ves (l, m, c) == ves (m+1, r, c) ) return false;
else return reshenie (l, m, c, metalon) || reshenie (m+1, r, c, metalon);
};

int main () {
vector<int> c[100];
int metalon, n, i;
ofstream outp ("output.txt");
ifstream inp ("input.txt");
inp >> metalon;
inp >> n;
for (i = 0; i < n; i++) inp >> c[i]; //ошибка 34 no match for 'operator>>' in 'inp >> c[i]'
if (reshenie (0, n, c, metalon) ) outp << "there is second etalon in array";
else outp << "there isn't second etalon in array";
return 0;
}

ЗЫ: 5я задача решена

неизвестный

# 8

= общий = | 11.10.2008, 18:05

Интересно, решит ли кто-нибудь задачу №4.....

Владимир (C4tnt)

# 9

= общий = | 11.10.2008, 22:24

Если задача выглядит так: "дано n-1 монеток одинакового веса и 2 монетки другого веса. Одну из этих двух монеток добавили к набору, вторая осталась в нашем распоряжении. Найти в наборе монетку - эталон" то можно искать примерно так:

1. Сравниваем случайную монетку из набора и эталон. Если они равны - случилось чудо smile (В общем, конец алгоритма). Если эталон больше весит - $T = "большая", если меньше - $T = "меньшая".

A:

2. Если в наборе осталась одна монетка - сравниваем её с эталоном и сообщаем о результате (конец алгоритма).
3. Делим набор монеток на три части. Две из них равны количественно, третья - произвольна (оптимальнее всего, когда все три части примерно равны)
4. Взвешиваем первые две части набора. Если они равны - убираем их из дальнейшего рассмотрения и идём к пункту A. Если среди них есть $T по весу - убираем
из набора всё, кроме этой части и идём к пункту A.

Вот, собственно, и был троичный поиск.

 

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

Rambler's Top100

главная страница | поддержка | задать вопрос

Время генерирования страницы: 0.15704 сек.

© 2001-2020, Портал RFPRO.RU, Россия
Калашников О.А.  |  Гладенюк А.Г.
Версия системы: 7.89 от 25.04.2020
Версия JS: 1.45 | Версия CSS: 3.39