Троичный поиск

Трои́чный по́иск (Тернарный поиск) — это метод в информатике для поиска максимумов и минимумов функции, которая либо сначала строго возрастает, затем строго убывает, либо наоборот. Троичный поиск определяет, что минимум или максимум не может лежать либо в первой, либо в последней трети области, и затем повторяет поиск на оставшихся двух третях. Троичный поиск демонстрирует парадигму программирования «разделяй и властвуй».

Функция

Предположим, что мы ищем максимум функции f(x), и что нам известно, что максимум лежит между A и B. Чтобы алгоритм был применим, должно существовать некоторое значение x, такое, что

  • для всех a, b, для которых A ≤ a < b ≤ x, выполняется f(a) < f(b), и
  • для всех a, b, для которых x ≤ a < b ≤ B, выполняется f(a) > f(b).

Алгоритм

/**
Находит максимум функции с одним экстремумом между l и r.
Чтобы найти минимум - достаточно поменять местами действия в ветках if/else.
*/
double l = ..., r = ..., EPS = ...; // входные данные
double m1, m2;
while (r - l > EPS) {
   m1 = l + (r - l) / 3; 
   m2 = r - (r - l) / 3;
   if (f (m1) < f (m2))
      l = m1;
   else
      r = m2;
}

См. также

Read other articles:

Strange Magic (film)

Halaman ini berisi artikel tentang film animasi komputer. Untuk lagu Strange Magic karya Electric Light Orchestra, lihat Strange Magic. Strange MagicPoster rilis bioskopSutradaraGary RydstromProduser Mark S. Miller Skenario David Berenbaum Irene Mecchi Gary Rydstrom CeritaGeorge LucasBerdasarkanImpian di Tengah Musimoleh William ShakespearePemeran Alan Cumming Evan Rachel Wood Kristin Chenoweth Maya Rudolph Sam Palladio Alfred Molina Penata musikMarius de VriesPenyuntingChris PlummerPer...

 

Evolusi KL Drift

Evolusi KL DriftPoster teatrikalSutradaraSyamsul YusofPemeranFasha SandhaFarid KamilSyamsul YusofAaron AzizIqram DinzlyDistributorSkop Productions Sdn BhdGrand Brilliance Sdn BhdTanggal rilis2008Negara MalaysiaBahasaBahasa MelayuAnggaran2 Juta Ringgit Evolusi KL Drift adalah film aksi asal Malaysia yang terinspirasi dari film The Fast and the Furious: Tokyo Drift. Film ini dirilis di Malaysia pada tanggal 3 April 2008. Sekuelnya Evolusi KL Drift 2 dirilis pada bulan Maret 2010. Pemeran Fasha ...

 

Butch McDonald

Canadian ice hockey player Ice hockey player Butch McDonald Butch McDonald (right), with Gus Giesebrecht, as members of the Pittsburgh Yellow Jackets in 1937.Born (1916-11-21)November 21, 1916Assiniboia, Saskatchewan, CanadaDied January 8, 2006(2006-01-08) (aged 89)British Columbia, CanadaHeight 6 ft 0 in (183 cm)Weight 185 lb (84 kg; 13 st 3 lb)Position Left wing/CentreShot LeftPlayed for Chicago Black HawksDetroit Red WingsPlaying career 1934–19...

Syndicat des avocats de France

Syndicat des avocats de FranceHistoireFondation 1973CadreSigle SAFType Syndicat professionnelForme juridique Ordre professionnel ou assimiléDomaine d'activité Activités des organisations professionnellesSiège Rue Saint-Lazare (34, 75009)Pays  FranceOrganisationFondateurs Jules Arrous (d), Serge Coche (d), Claude WillardPrésidente Judith KrivineSite web lesaf.orgIdentifiantsSIREN 329903025modifier - modifier le code - modifier Wikidata Le Syndicat des avocats de France (SAF) est une ...

 

Modélisme d'arsenal

Le modélisme naval est une activité de loisir[1], qui consiste à construire un modèle à échelle réduite des navires anciens en bois, principalement de l'époque du XVIIe et du XVIIIe siècle, à partir de monographies. Considéré, du point de vue « modélisme », comme le sommet de l'art, le modélisme d'arsenal oblige le modéliste à respecter dans les moindres détails non seulement l'apparence extérieure du navire, mais également les méthodes de construc...

 

Alexey Kornienko (politician)

Russian politician For other people named Alexey Kornienko, see Alexey Kornienko. In this name that follows Eastern Slavic naming customs, the patronymic is Victorovich and the family name is Kornienko. You can help expand this article with text translated from the corresponding article in Russian. (February 2024) Click [show] for important translation instructions. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must ...

Drainage Services Department

Hong Kong government department Drainage Services Department渠務署Government department overviewFormed1989HeadquartersRevenue TowerNo. 5 Gloucester Road, Wan ChaiEmployees2,064 (March 2022)[1]Annual budgetHK$3,447 million 2022-23 FY[1]Government department executiveAlice Pang, from 4 Nov. 2020[2], Director of Drainage ServicesWebsitedsd.gov.hk Drainage Services DepartmentTraditional Chinese渠務署Simplified Chinese渠务署TranscriptionsStandard MandarinHanyu...

 

Pathummayude Aadu

1959 novel by Vaikom Muhammad Basheer This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Pathummayude Aadu – news · newspapers · books · scholar · JSTOR (September 2018) (Learn how and when to remove this message) Pathumma's Goat First Edition CoverAuthorVaikom Muhammad BasheerOriginal titlePathummayude Aa...

 

Coast guard

Maritime security organization For the 1939 American film, see Coast Guard (film). For the 2002 South Korean film, see The Coast Guard (film). USCG National Security Cutter USCGC Bertholf (WMSL-750) and an EADS HC-144 Ocean Sentry Russian Coast Guard ship #183 Volga A CH-149 Cormorant training with a Canadian Coast Guard cutter A Chinese Coast Guard ship participating in an international exercise Multi-purpose vessel Arkona of the German Federal Coast Guard A Portuguese National Rep...

Большой Кадильный

Мыс Большой Кадильный Расположение 51°54′55″ с. ш. 105°13′20″ в. д.HGЯO АкваторияБайкал Страна Россия Субъект РФИркутская область Мыс Большой Кадильный Мыс Большой Кадильный Мыс Большо́й Кади́льный — мыс на юго-западном побережье Байкала в Иркутском районе Ирк�...

 

Министерство природных ресурсов и экологии Российской Федерации

Министерство природных ресурсов и экологии Российской Федерациисокращённо: Минприроды России Общая информация Страна  Россия Юрисдикция Россия Дата создания 12 мая 2008 Предшественники Министерство природных ресурсов Российской Федерации (1996—1998)Министерство охраны...

 

P2RY13

Protein-coding gene in the species Homo sapiens P2RY13Available structuresPDBOrtholog search: PDBe RCSB List of PDB id codes2B6UIdentifiersAliasesP2RY13, GPCR1, GPR86, GPR94, P2Y13, SP174, FKSG77, purinergic receptor P2Y13External IDsOMIM: 606380 MGI: 1921441 HomoloGene: 12543 GeneCards: P2RY13 Gene location (Human)Chr.Chromosome 3 (human)[1]Band3q25.1Start151,326,312 bp[1]End151,329,549 bp[1]Gene location (Mouse)Chr.Chromosome 3 (mouse)[2]Band3|3 DStart59...

哈萨克斯坦总统

此条目序言章节没有充分总结全文内容要点。 (2019年3月21日)请考虑扩充序言，清晰概述条目所有重點。请在条目的讨论页讨论此问题。 哈萨克斯坦總統哈薩克總統旗現任Қасым-Жомарт Кемелұлы Тоқаев卡瑟姆若马尔特·托卡耶夫自2019年3月20日在任任期7年首任努尔苏丹·纳扎尔巴耶夫设立1990年4月24日（哈薩克蘇維埃社會主義共和國總統） 哈萨克斯坦 哈萨克斯坦政府...

 

Anela

Anelacomune(IT) Anela(SC) Anèla Anela – Veduta LocalizzazioneStato Italia Regione Sardegna Provincia Sassari AmministrazioneSindacoGiangiuseppe Nurra (lista civica) dal 13-6-2022 TerritorioCoordinate40°26′40″N 9°03′29″E / 40.444444°N 9.058056°E40.444444; 9.058056 (Anela)Coordinate: 40°26′40″N 9°03′29″E / 40.444444°N 9.058056°E40.444444; 9.058056 (Anela) Altitudine446 m s.l.m. Superficie36,89 km...

 

I Left My Heart in San Francisco

1962 song popularized by Tony Bennett For the album, see I Left My Heart in San Francisco (album). I Left My Heart in San FranciscoPicture sleeve for early-1960s US single; the other US picture sleeve contains a photo of Tony BennettSingle by Tony Bennettfrom the album I Left My Heart in San Francisco - Columbia 1869 A-sideOnce Upon a TimeReleasedFebruary 2, 1962RecordedJanuary 23, 1962StudioCBS 30th Street Studio, New York City[1]GenreTraditional popLength2:52LabelColumbia 42332Compo...

فرد إميري

فرد إميري معلومات شخصية تاريخ الميلاد 27 أغسطس 1925   تاريخ الوفاة 10 أبريل 1997 (71 سنة)   مواطنة أستراليا  الحياة العملية المهنة عالم نفس  اللغات الإنجليزية  تعديل مصدري - تعديل   فرد إميري (بالإنجليزية: Fred Emery)‏ هو عالم نفس أسترالي، ولد في 27 أغسطس 1925، وتوفي في 10 أبري�...

 

Hyperbass flute

Extremely low-pitched musical instrument in the flute family Hyperbass fluteHyperbass flute played by Roberto Fabbriciani in Chemical Free (?) by Nicola Sani, 2014Woodwind instrumentClassification WindWoodwindAerophoneHornbostel–Sachs classification421.121.12-71(Side-blown Aerophone with tone holes and keys)Playing range The lowest note of the hyperbass flute is C0, below the lowest A on the concert piano.Related instruments Flutes: PiccoloTrebleSopranoFluteFlûte d'amourAltoBassContra-alto...

 

Histoire de la botanique

Buste de Théophraste, considéré comme le père de la botanique. L'histoire de la botanique est l'exposition et la narration des idées, des recherches et des travaux liés à la description, à la classification, au fonctionnement, à la distribution et aux relations des organismes appartenant aux règnes des Champignons, des Chromistes et des Plantes au cours des différentes périodes historiques[n 1],[n 2]. Depuis l'Antiquité, l'étude des plantes a été abordée selon deux approches ...

Eighth Army (United States)

Only Field Army of the U.S. Army stationed in South Korea This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Eighth Army United States – news · newspapers · books · scholar · JSTOR (April 2008) (Learn how and when to remove this message) Eighth ArmyEighth Army Shoulder Sleeve InsigniaActive10 June 1944 –...

 

تجزؤ الموطن

تجزؤ الموطن يشير إلى نشوء انقسامات (تجزؤات) في البيئة التي يحبذها الكائن الحي (موطنه)، مما يؤدي لتجزؤ التجمع. يمكن أن ينتج تجزؤ الموطن عن عمليات جيولوجية تعدل تدريجيًا بنية البيئة الفيزيائية (ويُعتقد أنها إحدى أهم مسببات الانتواع).[1] وقد تسببه أيضًا نشاطات الإنسان، بما ...