Собственно нужно найти наибольший элемент в матрице, который встречается > 1 раза. Помогите, пожалуйста, с алгоритмом.
3 ответа
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <set>
using namespace std;
int main()
{
int matrix[10][10];
srand(time(0));
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
matrix[i][j] = rand() % 50; // заполняем
}
}
set <int> myset;
set <int>::iterator it;
bool dupFound = false;
int maxValue;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
int v = matrix[i][j];
if (dupFound && v <= maxValue) continue;
it = myset.find(v);
if(it == myset.end())
myset.insert(v);
else {
maxValue = v;
if(!dupFound) dupFound = true;
}
}
}
for (int i = 0; i < 10; i++){
for (int j = 0; j < 10; j++) cout << setw(2) << matrix[i][j] << ' ';
cout << endl;
}
cout << maxValue << endl;
return 0;
}
#define SIZE 100
int array[SIZE];
bool have_such_number(int idx)
{
int n = array[idx];
for( ++idx; idx < SIZE; ++idx ) {
if( array[idx] == n ) return true;
}
return false;
}
int get_duplicated_maximum(void)
{
int max = INT_MIN;
for( int i = 0; i < SIZE; ++i ) {
if( array[i] > max && have_such_number(i) ) {
max = array[i];
}
}
return max;
}
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
int main(){
int matrix[10][10];
srand(time(0));
for (int i = 0; i < 10; i++){
for (int j = 0; j < 10; j++){
matrix[i][j] = rand() % 50; // заполняем
}
}
int max = 0;
for (int i = 0; i < 10; i++){
for (int j = 0; j < 10; j++){
if (matrix[i][j] > max)
max = matrix[i][j]; // находим наибольшее
}
}
int count = 0;
for (int i = 0; i < 10; i++){
for (int j = 0; j < 10; j++){
if (matrix[i][j] == max)
count++; // подсчитываем
}
}
for (int i = 0; i < 10; i++){
for (int j = 0; j < 10; j++){
cout << matrix[i][j] << "_"; // выводим
}
}
cout << endl << endl;
if (count > 1){
cout << "max digit:" << max << " count:" << count << endl; // выводим
}
return 0;
}
--------------------------переписано позднее
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>
using namespace std;
int main(){
int matrix[10][10];
vector<int> v;
srand(time(0));
for (int i = 0; i < 10; i++){
for (int j = 0; j < 10; j++){
matrix[i][j] = rand() % 50; // заполняем
}
}
int max = 0;
for (int i = 0; i < 10; i++){
for (int j = 0; j < 10; j++){
for (int a = i + 1; a < 10; a++){
for (int b = j + 1; b < 10; b++){
if (matrix[i][j] == matrix[a][b])
v.push_back(matrix[i][j]);
}
}
}
}
for (int i = 0; i < 10; i++){
for (int j = 0; j < 10; j++){
cout << matrix[i][j] << "_"; // выводим матрицу
}
}
cout << endl << "_______________________" << endl;
for (int i = 0; i < v.size(); i++){
cout << v[i] << "_"; // выводим вектор
}
for (int i = 0; i < v.size(); i++){
for (int j = 0; j < v.size(); j++){
if ((v[i] > v[j]) && (v[i] > max)){
max = v[i]; // находим наибольшее
}
}
}
cout << endl << "max:" << max << endl; // ответ
return 0;
}
-------------------добавлено позднее
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>
using namespace std;
int main(){
int matrix[10][10]; // = { 2, 2, 1, 1, 1, 1, 1, 1, 1 };
vector<int> v;
srand(time(0));
for (int i = 0; i < 10; i++){
for (int j = 0; j < 10; j++){
matrix[i][j] = rand() % 50; // заполняем
}
}
int max = 0;//, a = 0;
for (int i = 0; i < 10; i++){
for (int j = 0; j < 10; j++){
for (int a = i; a < 10; a++){
for (int b = j + 1; b < 10; b++){
if (matrix[i][j] == matrix[a][b]){
v.push_back(matrix[i][j]);
//break;
}
}
//a++;
}
}
}
for (int i = 0; i < 10; i++){
for (int j = 0; j < 10; j++){
cout << matrix[i][j] << "_";
}
}
cout << endl << "_______________________" << endl;
for (int i = 0; i < v.size(); i++){
cout << v[i] << "_";
}
if (v.size() != 0){
max = v[0];
}
for (int i = 0; i < v.size(); i++){
for (int j = 0; j < v.size(); j++){
if ((v[i] > v[j]) && (v[i] > max)){
max = v[i];
}
}
}
if (v.size() != 0){
cout << endl << "max:" << max << endl;
}
return 0;
}
-
В твоем случае получается, что мы по наибольшему элементу самой матрицы проверяем. А если будет так: 1 2 3 0 2 6 В таком случае правильный ответ 2, а не 6. Т.к. 6 встречается один раз, хоть и наибольший элемент в матрице. 26 дек 2012 в 7:43
-
действительно. сорри не уяснил суть вопроса, переписал. коряво правда немного– perfect26 дек 2012 в 7:49
-
Используйте map, где ключ -- значение из матрицы, а значение map -- количество вхождений.– alexlz26 дек 2012 в 9:54
-
2@perfect, а сами-то потестировать программу (уже переписанную) пробовали? -- 1). Что будет, если все ээлементы отрицательные? 2). Представьте матрицу 2 2 1 ... 1 1 1 .... 1 ..... 1 1 ..... 1 т.е. первые два (в нулевой строке) - двойки, а все остальные еденички. IMHO у Вас в
v
они не попадут. Идея-то Ваша понятна, поместить вv
все повторяющиеся элементы, а вот ее реализация хромает. 3) Зачем продолжать искать повторы (и заносить их вv
) после первого найденного? -- IMHO простейший алгоритм это скопировать матрицу, отсортровать ее и найти первый повтор.– avp26 дек 2012 в 15:29 -
единичкам попадать и не надо двойки больше единиц (ищем максимальное), а если есть отрицательные числа тогда переменную max инициализируем -65535 (если тип int). я этот код запускал раз 10 вроде работает. сказал сразу что код кривой немного. с проверкой кода на то чтоб прекращать цикл как только повтор найден не стал из за усложнения кода, да и расход тактов на проверку тоже увеличится– perfect26 дек 2012 в 16:04