Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Как доказать  (Прочитано 10847 раз)
0 Пользователей и 1 Гость смотрят эту тему.
The Nameless One
Помогающий

ru
Offline Offline
Пол: Мужской

« : 17-03-2011 21:14 » 

Как доказать тот факт, что сумма целых чисел от 1 до N равна (N * (N+1)) / 2 ?
Как это вывели, помогите понять, пожалуйста!
Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #1 : 17-03-2011 21:55 » 

Попробуйте для начала проверить это на нескольких конкретных примерах. По ходу станет совершенно очевидно, вывод очень простой.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
The Nameless One
Помогающий

ru
Offline Offline
Пол: Мужской

« Ответ #2 : 17-03-2011 21:56 » 

Проверил в уме на 1 + 2 + 3 + 4 + 5  = (5 * 6) / 2 = 15.
Возможно я туговат в таких вещах, но сформулировать доказательство словами не могу, так, что-то на уровне интуиции Улыбаюсь
Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #3 : 17-03-2011 22:01 » 

Попробуйте теперь складывать числа не подряд, а парами: первое с последним, второе - с предпоследним и т.д.
Для простоты сначала возьмем четное число элементов, чтобы все числа сложились в пары. Скажем, попробуйте для ряда от 1 до 10.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #4 : 17-03-2011 22:02 » 

шаг арифметической прогрессии чисел от 1 до N  равен 1
если принять первый за А, а шаг за d, последний за  N

A + (A + d) + (A + d +d ) ... и так N раз

а че я стараюсь? это вон в википедии есть  Жаль http://ru.wikipedia.org/wiki/%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #5 : 17-03-2011 22:49 » 

The Nameless One, подсказка:

(N * (N+1)) / 2  - площадь прямоугольного треугольника Улыбаюсь
Записан

The Nameless One
Помогающий

ru
Offline Offline
Пол: Мужской

« Ответ #6 : 17-03-2011 22:56 » 

Dale, Sla и Алексей1153++, спасибо!
Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #7 : 17-03-2011 22:57 » 

Теперь понятен вывод формулы?
Для нечетных N тоже вывели?
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #8 : 17-03-2011 23:03 » 

P.S. Настоятельно рекомендую проштудировать вот эту книгу:



Просто необходимый математический ликбез для программиста. Ликвидирует практически все пробелы в знаниях. По этой учебной программе сам Дональд Кнут учит своих студентов.

Книга не из самых дешевых, но стоит каждой заплаченной за нее копейки.
« Последнее редактирование: 17-03-2011 23:05 от Dale » Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #9 : 17-03-2011 23:05 » 

конкретная такая книга Улыбаюсь
Записан

Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #10 : 17-03-2011 23:10 » 

Да, для чиста конкретных пацанов-программистов. Кирпич весьма увесистый.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #11 : 18-03-2011 06:41 » 

Поскольку слово "математическая индукция" не прозвучало, то, наверное, стоит его озвучить Улыбаюсь
Шаг 1. Проверяем формулу для n=1. Очевидно, что 1*2/2 = 1, сумма верная
Шаг 2. Предположим, что для некоторого N=k всё работает. Т.е. Sum(k) = k(k+1)/2
Шаг 3. Проверим, как всё работает для k+1, сводя задачу к предыдущей: Sum(k+1) = (k+1) + Sum(k) = k + 1 + (k(k+1))/2 = (k(k+1) + 2(k+1)) / 2 = (k+2)(k+1) / 2. Что и требовалось доказать.
Поскольку из истинности k-того шага следует истинность k+1-го шага, и шаг для 1 верен, то индуктивно (рекурсивно) формула выводится для любого положительного целого N.

(Это что касается доказательства корректности, а не вывода, конечно Улыбаюсь )
« Последнее редактирование: 18-03-2011 06:44 от Вад » Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #12 : 18-03-2011 07:46 » 

вот так нагляднее некуда )) Хоть и не про войну.



12345  <<складываемые числа
     
    *
   **  << высота==5
  ***
 ****
*****  <<длина основания==5
     

площадь была бы 5*5/2, но учитываем, что диагональ добавляет 1/2 единицы площади за каждый элемент

S = (5*5/2) + (5/2)= N*N/2 + N/2 = (N+1)*N/2
Записан

The Nameless One
Помогающий

ru
Offline Offline
Пол: Мужской

« Ответ #13 : 18-03-2011 07:52 » 

Да, спасибо огромное, мужики! Улыбаюсь Теперь понял все.
И за книгу отдельное спасибо - очень нужная книженция, приобрету обязательно!
Записан
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #14 : 18-03-2011 09:59 » 

P.S. Настоятельно рекомендую проштудировать

Есть в ней серьёзные отличия от первого издания 1998 года? Та шла под подзаголовком "Основание информатики".

конкретная такая книга Улыбаюсь

Кстати, "конкретная" в данном случае акроним (наверное) "КОНтинуальная и дисКРЕТНАЯ" англ. CONCRETE -> СONtinous и disCRETE
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #15 : 18-03-2011 10:37 » 

Есть в ней серьёзные отличия от первого издания 1998 года? Та шла под подзаголовком "Основание информатики".

В оглавлении вообще не обнаружил никаких отличий. Второе издание имеет больше страниц (784 против 703), но это вполне может объясняться другой версткой. Другое издательство - "Вильямс" (первое - "Мир"), другой переводчик.

Кстати, это повторный перевод того же первоисточника, так что отличия, наверное, и искать не стоит (кроме примечаний переводчика).

Кстати, "конкретная" в данном случае акроним (наверное) "КОНтинуальная и дисКРЕТНАЯ" англ. CONCRETE -> СONtinous и disCRETE

Точно. И вдобавок еще один каламбур - "concrete" означает бетон. Кагбэ намек на фундаментальность.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #16 : 18-03-2011 13:08 » 

Ок, у меня просто 98-го года, а эта 2010-го, думал обновить, книга действительно мастхэв.
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines