Головоломка | 1000 лампочек включаются / выключаются 1000 проходящими мимо людьми

Опубликовано: 5 Января, 2022

Есть 1000 лампочек и 1000 человек. Все лампочки изначально выключены. Человек 1 щелкает лампочкой 1, 2, 3, 4,… человек 2, затем переворачивает 2, 4, 6, 8,… человек 3, затем 3, 6, 9,… и т.д., пока все 1000 человек не сделают это. Каково состояние лампочек 25, 93, 576, 132, 605, 26, 45, 37, 36 после того, как все люди перевернули свои соответствующие лампочки? Есть ли общее решение для прогнозирования состояния лампочки? Сколько лампочек горят после того, как прошли 1000 человек?

Пояснение: Основные наблюдения:

  1. Человек 1 щелкает лампочкой 1, 2, 3,… которые кратны 1.
  2. Человек 2 щелкает лампочкой 2, 4, 6,… которые кратны 2.
  3. Человек 3 щелкает лампочкой 3, 6, 9,… которые кратны 3.
  4. Точно так же Человек 1000 переворачивает лампочку 1000, что кратно 1000.
  5. Из приведенных выше наблюдений мы можем сказать, что человек i будет щелкать лампочки, кратные i,
  6. Таким образом, лампочку j перевернут все люди, для которых j кратно их личному числу. Другими словами, лампочку j перевернут все люди, у которых для человека номер i является коэффициентом j,
  7. Примеры:
    • (i) Лампочка 10 будет перевернута людьми 1, 2, 5, 10, чье количество людей кратно 10.
    • (ii) Лампочка 12 будет перевернута людьми 1, 2, 3, 4, 6, 12, чьи номера умножаются на 12.
  8. Таким образом, лампочка 25 будет перевернута людьми 1, 5, 25, поэтому она будет перевернута 3 раза, что является странным, и поскольку изначально все лампочки были «выключены», теперь лампочка 25 будет «включена».
  9. Лампочка 93 будет перевернута людьми 1, 3, 31, 93, поэтому она будет перевернута 4 раза, что является равным, и поскольку изначально все лампочки были «выключены», теперь лампочка 93 будет «выключена».
  10. Лампочку 576 перевернут люди 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 32, 36, 48, 64, 72, 96, 144, 192, 288, 576. , поэтому он будет перевернут 21 раз, что нечетно, поскольку изначально все лампочки были «выключены», теперь лампочка 576 будет «гореть».
  11. Лампочка 132 будет перевернута людьми 1, 2, 3, 4, 6, 11, 12, 22, 33, 44, 66, 132, поэтому она будет перевернута 12 раз, что является равномерным, и поскольку изначально все лампочки были «выключены», теперь лампочка 132 будет «выключена».
  12. Лампочка 605 будет перевернута людьми 1, 5, 11, 55, 121, 605, поэтому она будет перевернута 6 раз, что является равным, и поскольку изначально все лампочки были «выключены», теперь лампочка 605 будет «перевернута». выключенный".
  13. Лампочка 26 будет перевернута людьми 1, 2, 13, 26, поэтому она будет перевернута 4 раза, что является равным, и поскольку изначально все лампочки были «выключены», теперь лампочка 26 будет «выключена».
  14. Лампочка 45 будет перевернута людьми 1, 3, 5, 9, 15, 45, поэтому она будет перевернута 6 раз, что является равным, и поскольку изначально все лампочки были «выключены», теперь лампочка 45 будет «перевернута». выключенный".
  15. Лампочка 37, являющаяся лампочкой с основным номером, будет перевернута людьми 1, 37, поэтому она будет перевернута 2 раза, что является равным, и поскольку изначально все лампочки были «выключены», теперь лампочка 37 будет «выключена». ».
  16. Лампочка 36 будет перевернута людьми 1, 2, 3, 4, 6, 9, 12, 18, 36, поэтому она будет перевернута 9 раз, что нечетно, и, поскольку изначально все лампочки были «выключены», теперь лампочка 36 будет гореть.

Чтобы узнать состояние данной лампочки:
Мы подсчитываем количество факторов числа лампочек, и согласно вышеприведенным наблюдениям, если количество факторов нечетное, то лампочка будет «включена», а если она четная, то она будет «выключена» в конец.
Алгоритм определения количества лампочек, которые в итоге будут гореть:
Мы подсчитываем множители каждого числа от 1 до 1000. Если число множителей для любого числа нечетное, соответствующая лампочка горит, поэтому мы обновляем результат и, наконец, печатаем его.

Ниже приведен код, реализующий описанный выше алгоритм.

C ++

// C++ implementation of above approach
#include <iostream>
using namespace std;
int findOnBulbs( int numberOfBulbs)
{
// initializing the result
int onBulbs = 0;
// to loop over all bulbs from 1 to numberOfBulbs
int bulb = 1;
// to loop over persons to check whether their person number
int person = 1;
// is a factor of light bulb number or not
for (bulb = 1; bulb <= numberOfBulbs; bulb++) {
// inner loop to find factors of given bulb
// to count the number of factors of a given bulb
int factors = 0;
for (person = 1; person * person <= numberOfBulbs; person++) {
if (bulb % person == 0) // person is a factor
{
factors++;
// bulb != person*person
if (bulb / person != person)
{
factors++;
}
}
}
// if number of factors is odd, then the
if (factors % 2 == 1)
{
// light bulb will be "on" in the end
cout << "Light bulb "
<< bulb
<< " will be on"
<< " " ;
onBulbs++;
}
}
return onBulbs;
}
// Driver program to test above function
int main()
{
// total number of light bulbs
int numberOfBulbs = 1000;
// to find number of on bulbs in
// the end after all persons have
// flipped the light bulbs
int onBulbs = findOnBulbs(numberOfBulbs);
cout << "Total "
<< onBulbs
<< " light bulbs will be on in the end out of "
<< numberOfBulbs
<< " light bulbs"
<< " " ;
return 0;
}

Джава

// Java implementation of the
// above given approach
public class GFG
{
static int findOnBulbs( int numberOfBulbs)
{
// initializing the result
int onBulbs = 0 ;
// to loop over all bulbs from 1 to numberOfBulbs
int bulb = 1 ;
// to loop over persons to check whether their person number
int person = 1 ;
// is a factor of light bulb number or not
for (bulb = 1 ; bulb <= numberOfBulbs; bulb++) {
// inner loop to find factors of given bulb
// to count the number of factors of a given bulb
int factors = 0 ;
for (person = 1 ; person * person <= numberOfBulbs; person++) {
if (bulb % person == 0 ) // person is a factor
{
factors++;
// bulb != person*person
if (bulb / person != person)
{
factors++;
}
}
}
// if number of factors is odd, then the
if (factors % 2 == 1 )
{
// light bulb will be "on" in the end
System.out.println( "Light bulb " + bulb + " will be on" );
onBulbs++;
}
}
return onBulbs;
}
// Driver program to test above function
public static void main(String [] args)
{
// total number of light bulbs
int numberOfBulbs = 1000 ;
// to find number of on bulbs in
// the end after all persons have
// flipped the light bulbs
int onBulbs = findOnBulbs(numberOfBulbs);
System.out.println( "Total " + onBulbs
+ " light bulbs will be on in the end out of "
+ numberOfBulbs + " light bulbs" );
}
// This code is contributed
// by Ryuga
}

Python3

# Python3 code implementing the
# given approach
def findOnBulbs(numberOfBulbs):
# initializing the result
onBulbs = 0
# to loop over all bulbs from
# 1 to numberOfBulbs
bulb = 1
# to loop over persons to check
# whether their person number
person = 1
# Is a factor of light bulb number or not
for bulb in range ( 1 , numberOfBulbs + 1 ):
# inner loop to find factors of
# given bulb to count the number
# of factors of a given bulb
factors = 0
for person in range ( 1 , int (numberOfBulbs * * ( 0.5 )) + 1 ):
if bulb % person = = 0 : # person is a factor
factors + = 1
# bulb != person*person
if bulb / / person ! = person:
factors + = 1
# if number of factors is odd, then the
if factors % 2 = = 1 :
# light bulb will be "on" in the end
print ( "Light bulb" , bulb, "will be on" )
onBulbs + = 1
return onBulbs
# Driver Code
if __name__ = = "__main__" :
# total number of light bulbs
numberOfBulbs = 1000
# to find number of on bulbs in
# the end after all persons have
# flipped the light bulbs
onBulbs = findOnBulbs(numberOfBulbs)
print ( "Total" , onBulbs, "light bulbs will" ,
"be on in the end out of" ,
numberOfBulbs, "light bulbs" )
# This code is contributed
# by Rituraj Jain

C #

// C# implementation of above approach
using System;
class GFG
{
static int findOnBulbs( int numberOfBulbs)
{
// initializing the result
int onBulbs = 0;
// to loop over all bulbs from 1 to numberOfBulbs
int bulb = 1;
// to loop over persons to check whether their person number
int person = 1;
// is a factor of light bulb number or not
for (bulb = 1; bulb <= numberOfBulbs; bulb++) {
// inner loop to find factors of given bulb
// to count the number of factors of a given bulb
int factors = 0;
for (person = 1; person * person <= numberOfBulbs; person++) {
if (bulb % person == 0) // person is a factor
{
factors++;
// bulb != person*person
if (bulb / person != person)
{
factors++;
}
}
}
// if number of factors is odd, then the
if (factors % 2 == 1)
{
// light bulb will be "on" in the end
Console.WriteLine( "Light bulb " + bulb + " will be on" );
onBulbs++;
}
}
return onBulbs;
}
// Driver program to test above function
public static void Main()
{
// total number of light bulbs
int numberOfBulbs = 1000;
// to find number of on bulbs in
// the end after all persons have
// flipped the light bulbs
int onBulbs = findOnBulbs(numberOfBulbs);
Console.WriteLine( "Total " + onBulbs
+ " light bulbs will be on in the end out of "
+ numberOfBulbs + " light bulbs" );
}
}
// This code is contributed
// by Akanksha Rai

PHP

<?php
// PHP implementation of above approach
function findOnBulbs( $numberOfBulbs )
{
// initializing the result
$onBulbs = 0;
// to loop over all bulbs from
// 1 to numberOfBulbs
$bulb = 1;
// to loop over persons to check
// whether their person number
$person = 1;
// is a factor of light bulb number or not
for ( $bulb = 1;
$bulb <= $numberOfBulbs ; $bulb ++)
{
// inner loop to find factors of given
// bulb to count the number of factors
// of a given bulb
$factors = 0;
for ( $person = 1;
$person * $person <= $numberOfBulbs ; $person ++)
{
if ( $bulb % $person == 0) // person is a factor
{
$factors ++;
// bulb != person*person
if ( $bulb / $person != $person )
{
$factors ++;
}
}
}
// if number of factors is odd, then the
if ( $factors % 2 == 1)
{
// light bulb will be "on" in the end
echo "Light bulb " . $bulb .
" will be on" . " " ;
$onBulbs ++;
}
}
return $onBulbs ;
}
// Driver Code
// total number of light bulbs
$numberOfBulbs = 1000;
// to find number of on bulbs in
// the end after all persons have
// flipped the light bulbs
$onBulbs = findOnBulbs( $numberOfBulbs );
echo "Total " . $onBulbs . " light bulbs will " .
"be on in the end out of " . $numberOfBulbs .
" light bulbs" . " " ;
// This code is contributed by ita_c
?>

Javascript

<script>
// Javascript implementation of the
// above given approach
function findOnBulbs(numberOfBulbs)
{
// initializing the result
let onBulbs = 0;
// to loop over all bulbs from 1 to numberOfBulbs
let bulb = 1;
// to loop over persons to check whether their person number
let person = 1;
// is a factor of light bulb number or not
for (bulb = 1; bulb <= numberOfBulbs; bulb++) {
// inner loop to find factors of given bulb
// to count the number of factors of a given bulb
let factors = 0;
for (person = 1; person * person <= numberOfBulbs; person++) {
if (bulb % person == 0) // person is a factor
{
factors++;
// bulb != person*person
if (bulb / person != person)
{
factors++;
}
}
}
// if number of factors is odd, then the
if (factors % 2 == 1)
{
// light bulb will be "on" in the end
document.write( "Light bulb " + bulb + " will be on<br>" );
onBulbs++;
}
}
return onBulbs;
}
// Driver program to test above function
// total number of light bulbs
let numberOfBulbs = 1000;
// to find number of on bulbs in
// the end after all persons have
// flipped the light bulbs
let onBulbs = findOnBulbs(numberOfBulbs)
Technical Scripter

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Количество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023