Факториалӣ дар барномасозии Java

Имрӯз мо дар бораи омилҳо сӯҳбат хоҳем кард. Ин яке аз вазифаҳои асосӣест, ки барномасоз бояд донад ва ҳамзамон бо он кор карда тавонад. Пас биёед оғоз кунем. Факториали n арзиши ҳосor (зарбкунии) ҳамаи ададҳои натуралӣ аз 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 чӣ гуна хоҳад буд ва фаҳмем, ки чанд роҳе, ки бо онҳо факториалро ҳисоб кардан мумкин аст.

Ҳалли муқаррарӣ

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 эҷод мекунад. Баъдан, мо ҳама арзишҳоро бо истифода аз усули камкунӣ муттаҳид мекунем, яъне мо дар он нишон медиҳем, ки чӣ тавр мо мехоҳем онҳоро якҷоя кунем. Дар ниҳоят, мо бо истифода аз усули терминали 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ро аз печони ихтиёрӣ гирем ). Агар мо яке аз ин се усулро бо аргументи 100 иҷро кунем, он гоҳ мо изофа нахоҳем дошт ва мо ба даст меорем:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000