#include <stdio.h>
void main ()
{
int yArr[10][10] = {{0,0,0,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0,0},
{0,0,1,1,0,0,0,1,0,0},
{0,0,1,1,0,0,0,1,0,0},
{0,0,0,0,0,0,0,1,0,0},
{0,1,1,0,0,0,0,0,0,0},
{0,0,0,0,1,1,0,0,0,0},
{0,1,1,0,1,1,0,0,0,0},
{0,1,1,0,1,1,0,0,0,0},
{0,0,0,0,0,0,0,0,1,1}};
int i, j, count;
count = 0;
for (i = 0; i <= 9; i++)
{
for (j = 0; j <= 9; j++)
{
if ((yArr[j] == 1) && (yArr[j - 1] == 0) && (yArr[i - 1][j] == 0))
{
count = count + 1;
}
}
}
printf("Kolichestvo treugolnikov ravno %d", count);
}
Прямоугольники в квадрате
Привет. Есть задачка:
На квадратном клетчатом листе бумаги размером 10х10 клето нарисованно несколько прямоугольников. Каждый прямоугольник состоит из целых клеток, различные прямоугольники не накладываются друг на друга и не сопрекасаются.
Задан массив 10х10, в котором элемент A[i, j] = 1, если клетка принадлежит какому либо прямоугольнику, и A[i, j] = 0 в противном случае. Написать программу, которая сосчитает кол-во прямоугольников.
Пример:
const int m2[10][10]={{0,0,0,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0,0},
{0,0,1,1,0,0,0,1,0,0},
{0,0,1,1,0,0,0,1,0,0},
{0,0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,1,0,0},
{0,0,0,0,1,1,0,0,0,0},
{0,1,1,0,1,1,0,0,0,0},
{0,1,1,0,1,1,0,0,0,0},
{0,1,1,0,0,0,1,1,1,1}};
Здесь 5 прямоугольников. Пожайлуста помогите. Я знаю что нужно делать счетчик и условие, но вот как незнаю...
На квадратном клетчатом листе бумаги размером 10х10 клето нарисованно несколько прямоугольников. Каждый прямоугольник состоит из целых клеток, различные прямоугольники не накладываются друг на друга и не сопрекасаются.
Задан массив 10х10, в котором элемент A[i, j] = 1, если клетка принадлежит какому либо прямоугольнику, и A[i, j] = 0 в противном случае. Написать программу, которая сосчитает кол-во прямоугольников.
Пример:
const int m2[10][10]={{0,0,0,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0,0},
{0,0,1,1,0,0,0,1,0,0},
{0,0,1,1,0,0,0,1,0,0},
{0,0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,1,0,0},
{0,0,0,0,1,1,0,0,0,0},
{0,1,1,0,1,1,0,0,0,0},
{0,1,1,0,1,1,0,0,0,0},
{0,1,1,0,0,0,1,1,1,1}};
Здесь 5 прямоугольников. Пожайлуста помогите. Я знаю что нужно делать счетчик и условие, но вот как незнаю...
Псевдокод:
Цикл номера строки от 0 до 9
{
Цикл номера столбца от 0 до 9
{
Если текущая клетка равен 1, клетка сверху равен 0, клетка слева равен 0, то нашелся новый прямоугольник.
}
}
Реализуйте это.
Цикл номера строки от 0 до 9
{
Цикл номера столбца от 0 до 9
{
Если текущая клетка равен 1, клетка сверху равен 0, клетка слева равен 0, то нашелся новый прямоугольник.
}
}
Реализуйте это.
Цитата: Bonez92
Псевдокод:
Цикл номера строки от 0 до 9
{
Цикл номера столбца от 0 до 9
{
Если текущая клетка равен 1, клетка сверху равен 0, клетка слева равен 0, то нашелся новый прямоугольник.
}
}
Реализуйте это.
Цикл номера строки от 0 до 9
{
Цикл номера столбца от 0 до 9
{
Если текущая клетка равен 1, клетка сверху равен 0, клетка слева равен 0, то нашелся новый прямоугольник.
}
}
Реализуйте это.
Спасиб, все заработало... Я условие немного другое делал, проверял клетки ниже и клетку правей, а про это совсем забыл)
Цитата: xface
Спасиб, все заработало... Я условие немного другое делал, проверял клетки ниже и клетку правей, а про это совсем забыл)
Да и так должно было работать - если вы проверяли клетку ниже и клетку правей, и при этом правильно учли в программе, что клетки ниже / правей для проверяемой клетки может и не быть (если проверяемая клетка находится на нижней или правой границе массива).
Не большое уточнение:
Для данной матрицы все сработало и без этого уточнение, но если прямоуглоьник будет начинатся в крайнем левом столбце или верхней строке проверки (j-1) и (i-1) - вызовут ошибку либо возьмут совсем какое-то левое значение(не помню как в си с этим)
кстати, я не уверен что и мой способ сработает.. Я не уверен что в Си, при разборе условия A || B, при A=true условие B не проверяется.. кто точно знает, уточните в PHP, Java оно точно так.
Код:
#include <stdio.h>
void main ()
{
int yArr[10][10] = {{0,0,0,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0,0},
{0,0,1,1,0,0,0,1,0,0},
{0,0,1,1,0,0,0,1,0,0},
{0,0,0,0,0,0,0,1,0,0},
{0,1,1,0,0,0,0,0,0,0},
{0,0,0,0,1,1,0,0,0,0},
{0,1,1,0,1,1,0,0,0,0},
{0,1,1,0,1,1,0,0,0,0},
{0,0,0,0,0,0,0,0,1,1}};
int i, j, count;
count = 0;
for (i = 0; i <= 9; i++)
{
for (j = 0; j <= 9; j++)
{
if ((yArr[j] == 1) && ((j==0) || (yArr[j - 1] == 0)) && ((i==0) || (yArr[i - 1][j] == 0)))
{
count = count + 1;
}
}
}
printf("Kolichestvo treugolnikov ravno %d", count);
void main ()
{
int yArr[10][10] = {{0,0,0,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0,0},
{0,0,1,1,0,0,0,1,0,0},
{0,0,1,1,0,0,0,1,0,0},
{0,0,0,0,0,0,0,1,0,0},
{0,1,1,0,0,0,0,0,0,0},
{0,0,0,0,1,1,0,0,0,0},
{0,1,1,0,1,1,0,0,0,0},
{0,1,1,0,1,1,0,0,0,0},
{0,0,0,0,0,0,0,0,1,1}};
int i, j, count;
count = 0;
for (i = 0; i <= 9; i++)
{
for (j = 0; j <= 9; j++)
{
if ((yArr[j] == 1) && ((j==0) || (yArr[j - 1] == 0)) && ((i==0) || (yArr[i - 1][j] == 0)))
{
count = count + 1;
}
}
}
printf("Kolichestvo treugolnikov ravno %d", count);
Для данной матрицы все сработало и без этого уточнение, но если прямоуглоьник будет начинатся в крайнем левом столбце или верхней строке проверки (j-1) и (i-1) - вызовут ошибку либо возьмут совсем какое-то левое значение(не помню как в си с этим)
кстати, я не уверен что и мой способ сработает.. Я не уверен что в Си, при разборе условия A || B, при A=true условие B не проверяется.. кто точно знает, уточните в PHP, Java оно точно так.
Код:
#include <stdio.h>
int main()
{
int result, // Количество прямоугольников
up, // Верхняя клетка
left, // Левая клетка
current, // Текущая клетка
i, j;
const int m2[10][10]={
{0,0,0,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,1,1,0,0,0,0},
{0,1,1,0,1,1,0,0,0,0},
{0,1,1,0,1,1,0,0,0,0},
{0,1,1,0,0,0,1,1,1,1}};
result =0;
for (i=0; i<10; i++)
{
for (j=0; j<10; j++)
{
if (i==0)
{
up = 0;
} else {
up = m2[i-1][j];
}
if (j==0)
{
left = 0;
} else {
left = m2[j-1];
}
current = m2[j];
if ((current ==1)&&(left==0)&&(up==0)) result++;
}
}
printf ("Result is %d\n", result);
return 0;
}
int main()
{
int result, // Количество прямоугольников
up, // Верхняя клетка
left, // Левая клетка
current, // Текущая клетка
i, j;
const int m2[10][10]={
{0,0,0,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,1,1,0,0,0,0},
{0,1,1,0,1,1,0,0,0,0},
{0,1,1,0,1,1,0,0,0,0},
{0,1,1,0,0,0,1,1,1,1}};
result =0;
for (i=0; i<10; i++)
{
for (j=0; j<10; j++)
{
if (i==0)
{
up = 0;
} else {
up = m2[i-1][j];
}
if (j==0)
{
left = 0;
} else {
left = m2[j-1];
}
current = m2[j];
if ((current ==1)&&(left==0)&&(up==0)) result++;
}
}
printf ("Result is %d\n", result);
return 0;
}
Цитата: Lone Wolf
кстати, я не уверен что и мой способ сработает.. Я не уверен что в Си, при разборе условия A || B, при A=true условие B не проверяется.. кто точно знает, уточните в PHP, Java оно точно так.
Насколько я знаю сам, и судя по тому что написано здесь:
http://www.docs.hp.com/en/B3901-90007/ch05s10.html
это действительно так - в случае A || B условие B не проверяется, если выполнено условие A, а в случае A && B - условие B не проверяется, если условие A не выполнено:
[QUOTE="HP C/HP UX Reference Manual: HP UX Systems"]Logical operators (and the comma and conditional operators) are the only operators for which the order of evaluation of the operands is defined. The compiler must evaluate operands from left to right. Moreover, the compiler is guaranteed not to evaluate an operand if it is unnecessary. For example, in the expression
if ((a != 0) && (b/a == 6.0))
if a equals 0, the expression (b/a == 6) will not be evaluated. This rule can have unexpected consequences when one of the expressions contains side effects.[/QUOTE]
Стоит обратить внимание на последнюю фразу этой цитаты - если вы используете в каких-то условиях сложногосоставного условия какие-нибудь операции навроде i++ или вызовы функций, то, не зная этого правила и ожидая, что все части условия всегда вычисляются, можно получить баг. К вашему примеру это не относится, но в общем случае такой момент имеет место.
[QUOTE=Lone Wolf]
[/QUOTE]
Код:
if ((yArr[j] == 1) && ((j==0) || (yArr[j - 1] == 0)) && ((i==0) || (yArr[i - 1][j] == 0)))
{
count = count + 1;
}
{
count = count + 1;
}
Цитата: Bonez92
Код:
if (i==0)
{
up = 0;
} else {
up = m2[i-1][j];
}
if (j==0)
{
left = 0;
} else {
left = m2[j-1];
}
{
up = 0;
} else {
up = m2[i-1][j];
}
if (j==0)
{
left = 0;
} else {
left = m2[j-1];
}
Для оптимизации по скорости я бы не стал вводить эти условия в типичную итерацию, а либо расширил бы матрицу "бордюром", либо просто вынес бы проверку граничных условий за рамки общего цикла.
Предполагаю, что это повысило бы производительность на 30-40%.