Java - Цикли


0
Здравейте! Изучавам самостоятелно Java. Имам нужда от помощ относно глава 6 от книгата "Въвдение в програмирането с Java". Задачата е 11: напишете програма, която пресмята на колко нули завършва факториела на дадено число. Благодаря Ви!



Отговори



0

Разделяш си задачката на по-малки задачки. 1. Намираш факториела (използваш 1 цикъл) 2. Като резултат получаваш число на което те интересува колко са последните нули. Половината задача е решена:) Започваш да мислиш как да ги намериш колко са нулите. Може например да го делиш числото в един цикъл на 10 примерно и да гледаш остатъка при деление(%) дали е 0. Ако е 0, увеличаваш с едно стойността на една променлва, създадена със цел само да брои. При попадане на число остатък от делението различно от 0, сикъла бреак-ва и изписва резултата.

Друг вариант за решение е да го разглеждаш факториала като стринг и да вадиш последния елемент в един цикъл и пак да броиш.

Има заигравка при тази задача да се решава с добър перформанс като не изцикляш всичко навсякъде. Ето едно много добро обяснение на което попаднах.


от messenger (552 точки)


0

import java.util.Scanner;
 public class zadacha101 {
  public static void main(String[] args) {
   Scanner input = new Scanner(System.in);
   System.out.println("Enter a number");
   int n = input.nextInt();
   long factorial = 1;
   int a = 1;
   boolean equal = true;
   do {
   factorial *= n;
   n--;
   } while (n > 0);
   System.out.println("n! = " + factorial);
   for (int i = 0; i <= n; i++) {
    if (n % 10 == 0) {
     a++;
    } else {break;};
   } System.out.println(a);
            }
       }

Това е кода, който написах. Получава се, но има проблем. Показва ми само 2 нули. Тоест при въвеждане на факториел който има 3,4 и т.н. нули, програмата показва, че има 2 нули. Може ли малко помощ къде бъркам. Благодаря!




0

Предполагам, че най-простото решение което ти търсят в главата е да намериш факториела, да го направиш на стринг, да го обходиш отзад напред и да преброиш нулите.

Но вместо да правиш стринг и да обхождаш може да се провери с побитови операции колко са нулите. Или пък може да делиш числото с остатък на 10, след това да го делиш на 10 докато остатъка от деленето с остатък е нула.


от ivan.mihov1 (4988 точки)


1

Имахме такава задача в домашните по C#. За да преброиш нулите в края на факториела не е необходимо да го пресмяташ. Има си математически начин без да обхождаш големите числа (което е бавно). Потърси в Google за "factorial number of trailing zeros"... :-)

Успех!

P. S. Може да погледнеш моя код за това от ТУК.


от jorosoft (945 точки)


0
Първо намираш факториела на числото, после има варианти. Аз се сетих за 2 . Единия делиш факториела на %10 и ако остатъка е 0 увеличаваш броя на нулите, втория превръщаш факториела във стринг и пак броищ нулите отзад напред и като стигнеш до знак различен от "0" спираш да увеличаваш бройката.

от tanija (0 точки)


1

От чисто математическа гледна точка, а и от гледна точка сложност на алгоритъма и заемана памет, начина, който повечето хора предлагат - да се сметне първо факториела, после да се броят нулите, е доста излишно сложен.

n! има толкова нули, колкото пъти се дели на 10. 10=5*2. Един факториел винаги се дели повече пъти на 2, отколкото на 5 (всяко второ число се дели на 2, а на 5, всяко 5то). Затова за да преброим нулите накрая на един факториел, ни интересува всъщност колко пъти той се дели на 5.

Например 5!=5*4*3*2*1, веднъж се дели на 5, следователно има 1 нула накрая (и наистина 5!=120)

10! -> 2 пъти се дели на 5 -> 2 нули...

При 25! вече нулитe на факториела стават 6, защото 25=5*5.(плюс 1 нула за 5,10,15 и 20).

Тоест, за да преброиш нулите на n! можеш да пуснеш един цикъл с който да пресметнеш колко пъти n се дели на 5, на 5^2  и тн, докато 5^i е по-малко от n. Сумата на тези ще ти е броя на нулите... Това като C# код един колега вече го е публикувал. На java цикъла е същия.




0
Ето ТУК! има подробно описание как броенето да се случи бързо + елементарен код (n е числото, чиито факториел броим):
int count = 0; for (int i=5; n/i>=1; i *= 5){ count += n/i; } 

от Mironov (220 точки)