я нашел случайно, чтоC/C++ Integer Операция
int a = (h/2)*w+ ( (h+1)/2-h/2 ) * (w+1)/2 ;
равно
int b = (w * h + 1)/2 ;
когда ш и ч положительные целые числа (не берут на себя переполнение).
Можете ли вы показать мне, почему эти 2 одинаковы?
Редактировать: integer -> положительное целое число.
На самом деле это математическая проблема: (целое число)/2 следует интерпретировать как пол. Итак, проблема:
Показать, что
floor(h/2)*w + (floor((h+1)/2) - floor(h/2)) * floor((w+1)/2)эквивалентноfloor((w*h+1)/2)
Доказательство:
Подсказка: floor((2k+1)/2) == k. Вы можете легко показать эквивалентность.
Например, в случае 4:
а) floor(2k+1/2)*(2l+1) + (floor((2k+2)/2) - floor((2k+1)/2)) * floor((2l+2)/2) = 2kl+k + (k+1 - k)*(l+1) = 2kl + k + l + 1
б) floor(((2k+1)*(2l+1)+1)/2) = floor((4kl+2k+2l+2)/2) = 2kl + k + l + 1
Таким образом, эти два уравнения эквивалентны.
Для того, чтобы упростить ваше выражение, вы должны рассмотреть четыре случая:
Оттуда и применяя соответствующие правила усечения целых чисел, вы должны иметь возможность упростить свое второе выражение.
+1 для кусочков и кубиков для чего-то более простого. –
Забавный вопрос говорит о том, что он равен, и кажется, что он проверяет несколько четных и нечетных значений. Но это простая скучная математика, поэтому никто не проверяет все случаи. Я также был ленив, и, даже если я больше математики парня, я сделал быструю проверку компьютера с помощью нескольких копировать-вставить:
bool diff = false;
int n = 100;
for(int w = -n; w<n; ++w){
for(int h = -n; h<n; ++h){
int a = (h/2)*w+ ( (h+1)/2-h/2 ) * (w+1)/2 ;
int b = (w * h + 1)/2;
if (a!=b) diff = true;
}
}
cout << (diff ? "a != b" : "a == b") << endl;
И я обнаружил, что это не равно при со = -1 и Н = -1, легко проверить, что тогда a = 0 и b = 1. Вот как «приятное упрощение» часто вводит новую ошибку.
PS: Чтобы быть справедливым, я предполагаю, что w и h - ширина и высота, поэтому они, вероятно, всегда положительны. Но это не было указано (и, по опыту, какой-то другой код может вернуть отрицательную ширину)
спасибо за тестирование. да, я пропустил условие, что w и h положительны. Я отправил после такого тестирования. – sevity
Это прямой математический вопрос. Просто доказать следующее:
(H/2) * W + ((H + 1)/2-х/2) * (ш + 1)/2 = (W * H + 1)/2
В общем или для конкретных значений? Как вы обнаружили это случайно? –
И неправильная домашняя работа при этом. –
в целом. и это не домашнее задание. Я нашел его при решении проблемы с алгоритмом и сравнении моего решения с другим. – sevity