Java программалоодогу факториалдык

Бүгүн биз факториалдар жөнүндө сүйлөшөбүз. Бул программист бorши керек болгон эң негизги функциялардын бири жана ошол эле учурда аны менен иштей алат. Ошентип, баштайлы. n факториалы – 1ден nге чейинки бардык натурал сандардын көбөйтүлүшүнүн (көбөйтүлүшүнүн) мааниси, ал n катары белгиленет! Ал кандай көрүнөт:

1! =  1
2! =  1 * 2 = 2
3! =  1 * 2 * 3 = 6
4! =  1 * 2 * 3 * 4 = 24
5! =  1 * 2 * 3 * 4 * 5  = 120

Жана дагы бир кичинекей эреже, 0 үчүн:

!0  = 1

Эгерде биз, мисалы, фактордук айырманы 6 алууну кааласак! жана 4!:

6!-4! = 1⋅2⋅3⋅4⋅5⋅6 - 1⋅2⋅3⋅4 = 720 - 24 = 696

Келгиле, бул Java тorнде кандай болорун карап көрөлү жана факториалды эсептөөнүн бир нече жолдорун түшүнөбүз.

Кадимки чечим

public static int getFactorial(int f) {
  int result = 1;
  for (int i = 1; i <= f; i++) {
     result = result * i;
  }
  return result;
}

Эч нерсе татаал эмес: биз алынган санды циклибиздин өлчөмү катары колдонобуз, анда биз f жеткенге чейин бардык мурунку сандарга көбөйтөбүз. Жана негизгиси:

System.out.println(getFactorial(6) - getFactorial(4));

Биз текшерип, каалаган натыйжаны алабыз: 696.

Рекурсивдүү чечим

Рекурсия өзүнчө бир методду чакырып, кандайдыр бир логиканы жасайт. Бул ыкма рекурсивдүү деп аталат. Эреже катары, ал эки бөлүктөн турат:

1. ыкмадан чыгуу шарты, ага жеткенде ыкма өзүн чакырууну токтотуп, баалуулуктарды өткөрүп башташы керек. Болбосо, биз өз алдынча методду чакыруудан чексиз циклге ээ болобуз жана натыйжада StackOverflowError .

2. кээ бир иштетүү (логика) белгилүү бир кырдаалда зарыл + өзүн чакырып, бирок башка кириш мааниси менен.

Биздин бүгүнкү рекурсия үчүн идеалдуу мисал факториалды табуу болуп саналат:

public static int getFactorial(int f) {
  if (f <= 1) {
     return 1;
  }
  else {
     return f * getFactorial(f - 1);
  }
}

1ге жеткенде рекурсиядан чыгуунун шартын коёбуз. Эгерде аргумент 1 эмес болсо, анда биз учурдагы маанини ушул методго кийинки чакыруунун натыйжасына көбөйтөбүз (бул жерде биз учурдагы маанини -1 жөнөтөбүз).

Stream менен чечим

Агым функциясын билбегендер же эс тутумун жаңырткысы келгендер үчүн муну окуу пайдалуу болот .

public static int getFactorial(int f) {
  if (f <= 1) {
     return 1;
  }
  else {
     return IntStream.rangeClosed(2, f).reduce((x, y) -> x * y).getAsInt();
  }
}

Бул жерде биз IntStream атайын классын колдонобуз, ал int маанилерден агым менен иштөөдө кошумча мүмкүнчүлүктөрдү берет. Мындай агымды түзүү үчүн биз анын 2ден f камтылган 1 кадамы менен маанилерди түзгөн rangeClosed статикалык ыкмасын колдонобуз. Андан кийин биз бардык маанилерди азайтуу ыкмасы менен бириктиребиз, тактап айтканда, биз анда кантип биз аларды бириктиргибиз келет. Акыр-аягы, биз getAsInt терминалдык ыкмасын колдонуу менен алынган маанини алабыз.

BigInteger колдонуу

Javaда BigInteger классы көбүнчө сандарды, өзгөчө BIG сандарды иштетүү үчүн колдонулат . Анткени, эгерде биз int колдонсок, анда биз маалыматтарды жоготпостон ала турган максималдуу факториал 31, узакка - 39. Бирок 100 факториалы керек болсочы? Келгиле, мурунку чечимдерди карап көрөлү, бирок BigInteger колдонуп.

Кадимки чечим

public static BigInteger getFactorial(int f) {
  BigInteger result = BigInteger.ONE;
  for (int i = 1; i <= f; i++)
     result = result.multiply(BigInteger.valueOf(i));
  return result;
}

Эсептөө алгоритми негизинен окшош, бирок бул жерде биз BigIntegerдин мүмкүнчүлүктөрүн колдонобуз: BigInteger.ONE - баштапкы маанини 1ге коюу үчүн. көбөйтүү - мурунку фактордук маани менен учурдагы санды көбөйтүү.

Рекурсивдүү чечим

public static BigInteger getFactorial(int f) {
  if (f <= 1) {
     return BigInteger.valueOf(1);
  }
  else {
     return BigInteger.valueOf(f).multiply(getFactorial(f - 1));
  }
}

Чечимдин жалпы логикасы өзгөрбөйт, бирок BigInteger менен иштөө үчүн кээ бир методдор кошулган.

Stream менен чечим

public static BigInteger getFactorial(int f) {
  if (f < 2) {
     return BigInteger.valueOf(1);
  }
  else {
     return IntStream.rangeClosed(2, f).mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get();
  }
}

Негизи баары бирдей, бирок BigInteger менен. Агымда азыр бизде mapToObj ыкмасы бар, анын жардамы менен биз int маанилерин BigIntegerге айландырабыз, аларды кийинчерээк көбөйтүү аркылуу көбөйтүү (жакшы, биз Кошумча орогучтан an object алуу үчүн get коштук ) . Эгерде биз бул үч ыкманын бирин 100 аргументи менен иштетсек, анда толуп кетпейбиз жана биз төмөнкүнү алабыз:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000