Как лучше всего решить проблему «Студенты и шкафчики»?

Question

Я подумал, что было бы интересно представить некоторые классические проблемы с CS и позволить людям показать свои навыки оптимизации алгоритмов. Мы надеемся, что нам удастся увидеть некоторые умные методы для решения абстрактных задач, которые мы сможем реализовать на практике.

В идеале решения должны быть представлены в псевдокоде с большой O классификацией Доказательством этой классификации является соус. На проблему:

Есть N закрытых шкафчиков и N студентов. Первый студент открывает каждый шкафчик. Второй студент открывает или закрывает каждый второй шкафчик. Это продолжается, когда n-й студент открывает и закрывает каждый n-й шкафчик. После N студентов какие шкафчики открыты? Сколько шкафчиков открыто?

Answer 1

Учащиеся будут менять состояние только тех шкафчиков, для которых их число делится (ученик 2 переворачивает четные шкафчики, ученик 3 переворачивает шкафчики, делимые на 3, и так далее ...). Таким образом, единственные блокираторы, которые останутся открытыми после N раундов, - это те, которые имеют нечетное количество делителей (поскольку они начинают закрываться, нечетное количество бросков оставляет его открытым). Единственные числа с нечетным числом делителей - это идеальные квадраты, поэтому все запирающиеся шкафчики с идеальными квадратами останутся открытыми. Таким образом, после N раундов количество открытых шкафчиков будет квадратным корнем (с полами) из N.

Это решение будет O (sqrt (N)), чтобы знать , какие именно шкафчики открыты, но O (1), если вам нужно только сколько шкафчиков открыто .

Answer 2

Вот мой ответ без использования массивов (или объектов и т. Д.) И без использования метода квадратного корня.

====

включает

с использованием пространства имен std;

int main () {

int studentTotal, lockerTotal, visit, totalOpened = 0, totalClosed = 0;

cout << «Введите количество студентов» << endl; cin >> studentTotal;

lockerTotal = studentTotal;

for (int locker = 1; locker <= lockerTotal;  locker++ ){ // locker loop
    cout << "\n\n\nLocker no." << locker << endl;
    cout << " is visited by student(s) ";
    visit = 0;
    for (int student = 1 ; student <= studentTotal; student++) { // student loop

    if( locker % student == 0) {
            cout << student << ", ";
            visit++;}

    }//end of locker loop

    cout << "\nTotal number of visits: " << visit;
    if (visit % 2 == 0){
        cout << " the locker will stay closed.";
        totalClosed++;}
    else { cout << " the locker will be opened.";
        totalOpened++;}

} //end of student loop

if (lockerTotal == totalOpened + totalClosed) {
    cout << "\n\n\nOf total lockers (" << lockerTotal << "), " << totalOpened << " will be left open." << "(" << totalClosed << ") " << "will be closed." << endl;
    }else cout << "Error!!";



return 0;

}

Answer 3

Простое решение с наименьшим кодом.

Автор: Моаззам Али

   public class CH3 {

`public static void main (String [] args) { логические [] шкафчики = новый логический [100];

    for(int i=0;i<100;i++){
        lockers[i]=true;
                          }

    for(int s=2;s<100;s++){
        for(int y=s; y<100;y=y+s){
            if(lockers[y]==true){
                lockers[y]=false;
                               }
            else{
                lockers[y]=true;
                }
                              }
                          }
System.out.println("open lockers are:");
for(int i=0;i<100;i++){
if(lockers[i]==true){


System.out.print(i+"  ");
}
}   

}}

Answer 4

Ниже приведен код Java с использованием метода грубой силы. Он проверяет каждого учащегося и то, что он делает с каждым конкретным шкафчиком. Есть лучший подход. Предположим, есть 100 студентов и 100 шкафчиков. Затем Шестой шкафчик будет затронут Студентом 1, Студентом 2 и Студентом 3. 1X1, 2X3, 3X2. Но только в шкафчиках с квадратами четное число студентов будет касаться их.

Таким образом, лучше всего найти квадраты между числами.

Java-код:

  int l, s;
  Scanner in = new Scanner(System.in);
  System.out.println("Enter the number of lockers");
  l = in .nextInt();
  System.out.println("Enter the number of students");
  s = in .nextInt();
  if (l

   boolean lockers[] = new boolean[l + 1]; 
   boolean students[] = new boolean[s + 1]; lockers[0] = true; students[0] = true;
   for (int i = 1; i <= l; i++) {
lockers[i] = false;
   }

   for (int j = 1; j <= s; j++) {
for (int h = 1; h <= l; h++) {
 if (h % j == 0) {
  if (lockers[h] == true) lockers[h] = false;
  else lockers[h] = true;
 }

}
 }
   System.out.println("the lockers which are open are ");
   for (int k = 1; k <= l; k++) {
       if (lockers[k] == true) {
       System.out.print(" " + k);
   }
 }

Answer 5

Только что это было задание hw.

for(int i = 0; i < SIZE / 2; i++){
   for(int k = i; k < SIZE; k = k+i+1){
      if(lockers[k] == false)
        lockers[k] = true;
      else
        lockers[k] = false;
   }
}

Answer 6

Я думал, что увижу, как быстро я смогу найти решение в Perl.

use strict;
use warnings;
use 5.010;

sub lockers{
  my($number_of_lockers) = @_;

  my $largest_sqrt = sqrt $number_of_lockers;

  my @list;

  for( my $index = 1; $index <= $largest_sqrt; ++$index ){
    push @list, $index**2;
  }

  return @list;
}

say for lockers 100;

1
4
9
16
25
36
49
64
81
100

Или, если вы не хотите вычислять квадратный корень из числа шкафчиков.

use strict;
use warnings;
use 5.010;

sub lockers{
  my($number_of_lockers) = @_;

  my @list;

  for(
    my($index,$sqr) = (1,1);
    $sqr <= $number_of_lockers;
    $sqr = (++$index)**2
  ){
    push @list, $sqr;
  }

  return @list;
}

say for lockers 100;

Answer 7

В O (log N) на основе интервала открытых шкафчиков, следующих за сериями 1 + 2k:

delta=1

for(index=1;index < N;index+=delta) {
   print open locker = index;
   delta+=2;
   opencount++;
};