Как управлять компилятором С#, С++ или Java для вычисления 1 + 2 + 3 +... + 1000?
В недавнем интервью мне задали действительно странный вопрос. Интервьюер спросил меня, как я могу вычислить 1 + 2 + 3 +... + 1000, просто используя функции компилятора. Это означает, что мне не разрешено писать программу и выполнять ее, но я должен просто написать программу, которая могла бы заставить компилятор вычислить эту сумму во время компиляции и распечатать результат при завершении компиляции. В качестве подсказки он сказал мне, что я могу использовать генераторы и препроцессорные функции компилятора. Можно использовать компилятор С++, С# или Java. Любые идеи???
Этот вопрос не связан с вычислением суммы без каких-либо циклов здесь. Кроме того, следует отметить, что сумма СЛЕДУЕТ рассчитываться во время компиляции. Печать только результата с использованием директив компилятора С++ неприемлема.
Читая больше о опубликованных ответах, я обнаружил, что решение проблем во время компиляции с использованием шаблонов С++ называется метапрограммированием. Это метод, который случайно был обнаружен д-ром Эрвином Унрухом во время процесса стандартизации языка С++. Вы можете узнать больше об этой теме на странице вики-страницы метапрограммирования.
Кажется, что можно написать программу на Java, используя аннотации java. Вы можете посмотреть ниже maress.
Хорошая книга о мета-программировании на С++ - это этот. Стоит взглянуть, если интересно.
Полезной библиотекой мета-программирования С++ является Boost MPL эта ссылка.
Ответы
Ответ 1
Обновлено Теперь с улучшенной глубиной рекурсии! Работает на MSVC10 и GCC без увеличения глубины.:)
Простая рекурсия времени компиляции + добавление:
template<unsigned Cur, unsigned Goal>
struct adder{
static unsigned const sub_goal = (Cur + Goal) / 2;
static unsigned const tmp = adder<Cur, sub_goal>::value;
static unsigned const value = tmp + adder<sub_goal+1, Goal>::value;
};
template<unsigned Goal>
struct adder<Goal, Goal>{
static unsigned const value = Goal;
};
Testcode:
template<unsigned Start>
struct sum_from{
template<unsigned Goal>
struct to{
template<unsigned N>
struct equals;
typedef equals<adder<Start, Goal>::value> result;
};
};
int main(){
sum_from<1>::to<1000>::result();
}
Выход для GCC:
error: объявление 'struct sum_from < 1u > :: to < 1000u > :: equals < 500500u >
Пример Live на Ideone.
Выход для MSVC10:
error C2514: 'sum_from<Start>::to<Goal>::equals<Result>' : class has no constructors
with
[
Start=1,
Goal=1000,
Result=500500
]
Ответ 2
Пример С# для ошибки во время компиляции.
class Foo
{
const char Sum = (1000 + 1) * 1000 / 2;
}
Производит следующую ошибку компиляции:
Constant value '500500' cannot be converted to a 'char'
Ответ 3
Я должен просто написать программу, которая могла бы заставить компилятор вычислить эту сумму во время компиляции и распечатать результат при завершении компиляции.
Популярный трюк для печати числа во время компиляции пытается получить доступ к несуществующему члену шаблона, созданного с номером, который вы хотите распечатать:
template<int> struct print_n {};
print_n<1000 * 1001 / 2>::foobar go;
Затем компилятор говорит:
error: 'foobar' in 'struct print_n<500500>' does not name a type
Для более интересного примера этой техники см. Решите проблему восьми ферзей во время компиляции.
Ответ 4
Поскольку ни один компилятор и язык не были указаны в вопросе интервью, я смею представить решение в Haskell с помощью GHC:
{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS_GHC -ddump-splices #-}
module Main where
main :: IO ()
main = print $(let x = sum [1 :: Int .. 1000] in [| x |])
Скомпилируйте его:
$ ghc compsum.hs
[1 of 1] Compiling Main ( compsum.hs, compsum.o )
Loading package ghc-prim ... linking ... done.
<snip more "Loading package ..." messages>
Loading package template-haskell ... linking ... done.
compsum.hs:6:16-56: Splicing expression
let x = sum [1 :: Int .. 1000] in [| x |] ======> 500500
Linking compsum ...
И у нас также есть рабочая программа.
Ответ 5
Жизнь будет намного проще с С++ 11, которая добавляет функции constexpr для вычисления времени компиляции, хотя они только в настоящее время поддерживают gcc 4.6 или новее.
constexpr unsigned sum(unsigned start, unsigned end) {
return start == end ? start :
sum(start, (start + end) / 2) +
sum((start + end) / 2 + 1, end);
}
template <int> struct equals;
equals<sum(1,1000)> x;
Стандарт требует, чтобы компилятор поддерживал глубину рекурсии 512, поэтому ему все равно необходимо избегать глубины рекурсивной рекурсии. Здесь вывод:
$ g++-mp-4.6 --std=c++0x test.cpp -c
test.cpp:8:25: error: aggregate 'equals<500500> x' has incomplete type and cannot be defined
Конечно, вы можете просто использовать формулу:
constexpr unsigned sum(unsigned start, unsigned end) {
return (start + end) * (end - start + 1) / 2;
}
// static_assert is a C++11 assert, which checks
// at compile time.
static_assert(sum(0,1000) == 500500, "Sum failed for 0 to 1000");
Ответ 6
В java я подумал об использовании обработки аннотаций.
Инструмент apt сканирует исходный файл перед фактическим анализом исходного файла на команду javac.
Во время компиляции исходных файлов вывод будет распечатан:
@Documented
@Retention(RetentionPolicy.RUNTIME)
@Target({ElementType.TYPE, ElementType.METHOD})
public @interface MyInterface {
int offset() default 0;
int last() default 100;
}
Процессор factory:
public class MyInterfaceAnnotationProcessorFactory implements AnnotationProcessorFactory {
public Collection<String> supportedOptions() {
System.err.println("Called supportedOptions.............................");
return Collections.EMPTY_LIST;
}
public Collection<String> supportedAnnotationTypes() {
System.err.println("Called supportedAnnotationTypes...........................");
return Collections.singletonList("practiceproject.MyInterface");
}
public AnnotationProcessor getProcessorFor(Set<AnnotationTypeDeclaration> set, AnnotationProcessorEnvironment ape) {
System.err.println("Called getProcessorFor................");
if (set.isEmpty()) {
return AnnotationProcessors.NO_OP;
}
return new MyInterfaceAnnotationProcessor(ape);
}
}
Фактический обработчик аннотации:
public class MyInterfaceAnnotationProcessor implements AnnotationProcessor {
private AnnotationProcessorEnvironment ape;
private AnnotationTypeDeclaration atd;
public MyInterfaceAnnotationProcessor(AnnotationProcessorEnvironment ape) {
this.ape = ape;
atd = (AnnotationTypeDeclaration) ape.getTypeDeclaration("practiceproject.MyInterface");
}
public void process() {
Collection<Declaration> decls = ape.getDeclarationsAnnotatedWith(atd);
for (Declaration dec : decls) {
processDeclaration(dec);
}
}
private void processDeclaration(Declaration d) {
Collection<AnnotationMirror> ams = d.getAnnotationMirrors();
for (AnnotationMirror am : ams) {
if (am.getAnnotationType().getDeclaration().equals(atd)) {
Map<AnnotationTypeElementDeclaration, AnnotationValue> values = am.getElementValues();
int offset = 0;
int last = 100;
for (Map.Entry<AnnotationTypeElementDeclaration, AnnotationValue> entry : values.entrySet()) {
AnnotationTypeElementDeclaration ated = entry.getKey();
AnnotationValue v = entry.getValue();
String name = ated.getSimpleName();
if (name.equals("offset")) {
offset = ((Integer) v.getValue()).intValue();
} else if (name.equals("last")) {
last = ((Integer) v.getValue()).intValue();
}
}
//find the sum
System.err.println("Sum: " + ((last + 1 - offset) / 2) * (2 * offset + (last - offset)));
}
}
}
}
Затем мы создаем исходный файл. простой класс, который использует аннотацию MyInterface:
@MyInterface(offset = 1, last = 1000)
public class Main {
@MyInterface
void doNothing() {
System.out.println("Doing nothing");
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Main m = new Main();
m.doNothing();
MyInterface my = (MyInterface) m.getClass().getAnnotation(MyInterface.class);
System.out.println("offset: " + my.offset());
System.out.println("Last: " + my.last());
}
}
Обработчик аннотации компилируется в файл jar, тогда инструмент apt используется для компиляции исходного файла как:
apt -cp "D:\Variance project\PracticeProject\dist\practiceproject.jar" -factory practiceproject.annotprocess.MyInterfaceAnnotationProcessorFactory "D:\Variance project\PracticeProject2\src\practiceproject2\Main.java"
Результат проекта:
Called supportedAnnotationTypes...........................
Called getProcessorFor................
Sum: 5000
Sum: 500500
Ответ 7
Вот реализация, которая работает под VС++ 2010. Мне пришлось разбивать вычисления на 3 этапа, так как компилятор жаловался, когда шаблоны повторялись 500 раз.
template<int t_startVal, int t_baseVal = 0, int t_result = 0>
struct SumT
{
enum { result = SumT<t_startVal - 1, t_baseVal, t_baseVal + t_result +
t_startVal>::result };
};
template<int t_baseVal, int t_result>
struct SumT<0, t_baseVal, t_result>
{
enum { result = t_result };
};
template<int output_value>
struct Dump
{
enum { value = output_value };
int bad_array[0];
};
enum
{
value1 = SumT<400>::result, // [1,400]
value2 = SumT<400, 400, value1>::result, // [401, 800]
value3 = SumT<200, 800, value2>::result // [801, 1000]
};
Dump<value3> dump;
Когда вы скомпилируете это, вы должны увидеть этот вывод из компилятора примерно так:
1>warning C4200: nonstandard extension used : zero-sized array in struct/union
1> Cannot generate copy-ctor or copy-assignment operator when UDT contains a
zero-sized array
1> templatedrivensum.cpp(33) : see reference to class template
instantiation 'Dump<output_value>' being compiled
1> with
1> [
1> output_value=500500
1> ]
Ответ 8
Я чувствую себя обязанным давать этот код C, поскольку никто еще не имеет:
#include <stdio.h>
int main() {
int x = 1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+
21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39+40+
41+42+43+44+45+46+47+48+49+50+51+52+53+54+55+56+57+58+59+60+
61+62+63+64+65+66+67+68+69+70+71+72+73+74+75+76+77+78+79+80+
81+82+83+84+85+86+87+88+89+90+91+92+93+94+95+96+97+98+99+100+
101+102+103+104+105+106+107+108+109+110+111+112+113+114+115+116+117+118+119+120+
121+122+123+124+125+126+127+128+129+130+131+132+133+134+135+136+137+138+139+140+
141+142+143+144+145+146+147+148+149+150+151+152+153+154+155+156+157+158+159+160+
161+162+163+164+165+166+167+168+169+170+171+172+173+174+175+176+177+178+179+180+
181+182+183+184+185+186+187+188+189+190+191+192+193+194+195+196+197+198+199+200+
201+202+203+204+205+206+207+208+209+210+211+212+213+214+215+216+217+218+219+220+
221+222+223+224+225+226+227+228+229+230+231+232+233+234+235+236+237+238+239+240+
241+242+243+244+245+246+247+248+249+250+251+252+253+254+255+256+257+258+259+260+
261+262+263+264+265+266+267+268+269+270+271+272+273+274+275+276+277+278+279+280+
281+282+283+284+285+286+287+288+289+290+291+292+293+294+295+296+297+298+299+300+
301+302+303+304+305+306+307+308+309+310+311+312+313+314+315+316+317+318+319+320+
321+322+323+324+325+326+327+328+329+330+331+332+333+334+335+336+337+338+339+340+
341+342+343+344+345+346+347+348+349+350+351+352+353+354+355+356+357+358+359+360+
361+362+363+364+365+366+367+368+369+370+371+372+373+374+375+376+377+378+379+380+
381+382+383+384+385+386+387+388+389+390+391+392+393+394+395+396+397+398+399+400+
401+402+403+404+405+406+407+408+409+410+411+412+413+414+415+416+417+418+419+420+
421+422+423+424+425+426+427+428+429+430+431+432+433+434+435+436+437+438+439+440+
441+442+443+444+445+446+447+448+449+450+451+452+453+454+455+456+457+458+459+460+
461+462+463+464+465+466+467+468+469+470+471+472+473+474+475+476+477+478+479+480+
481+482+483+484+485+486+487+488+489+490+491+492+493+494+495+496+497+498+499+500+
501+502+503+504+505+506+507+508+509+510+511+512+513+514+515+516+517+518+519+520+
521+522+523+524+525+526+527+528+529+530+531+532+533+534+535+536+537+538+539+540+
541+542+543+544+545+546+547+548+549+550+551+552+553+554+555+556+557+558+559+560+
561+562+563+564+565+566+567+568+569+570+571+572+573+574+575+576+577+578+579+580+
581+582+583+584+585+586+587+588+589+590+591+592+593+594+595+596+597+598+599+600+
601+602+603+604+605+606+607+608+609+610+611+612+613+614+615+616+617+618+619+620+
621+622+623+624+625+626+627+628+629+630+631+632+633+634+635+636+637+638+639+640+
641+642+643+644+645+646+647+648+649+650+651+652+653+654+655+656+657+658+659+660+
661+662+663+664+665+666+667+668+669+670+671+672+673+674+675+676+677+678+679+680+
681+682+683+684+685+686+687+688+689+690+691+692+693+694+695+696+697+698+699+700+
701+702+703+704+705+706+707+708+709+710+711+712+713+714+715+716+717+718+719+720+
721+722+723+724+725+726+727+728+729+730+731+732+733+734+735+736+737+738+739+740+
741+742+743+744+745+746+747+748+749+750+751+752+753+754+755+756+757+758+759+760+
761+762+763+764+765+766+767+768+769+770+771+772+773+774+775+776+777+778+779+780+
781+782+783+784+785+786+787+788+789+790+791+792+793+794+795+796+797+798+799+800+
801+802+803+804+805+806+807+808+809+810+811+812+813+814+815+816+817+818+819+820+
821+822+823+824+825+826+827+828+829+830+831+832+833+834+835+836+837+838+839+840+
841+842+843+844+845+846+847+848+849+850+851+852+853+854+855+856+857+858+859+860+
861+862+863+864+865+866+867+868+869+870+871+872+873+874+875+876+877+878+879+880+
881+882+883+884+885+886+887+888+889+890+891+892+893+894+895+896+897+898+899+900+
901+902+903+904+905+906+907+908+909+910+911+912+913+914+915+916+917+918+919+920+
921+922+923+924+925+926+927+928+929+930+931+932+933+934+935+936+937+938+939+940+
941+942+943+944+945+946+947+948+949+950+951+952+953+954+955+956+957+958+959+960+
961+962+963+964+965+966+967+968+969+970+971+972+973+974+975+976+977+978+979+980+
981+982+983+984+985+986+987+988+989+990+991+992+993+994+995+996+997+998+999+1000;
printf("%d\n", x);
}
И все, что мне нужно сделать, это проверить сборку, чтобы найти мой ответ!
gcc -S compile_sum.c;
grep "\$[0-9]*, *-4" compile_sum.s
И я вижу:
movl $500500, -4(%rbp)
Ответ 9
Продленный от Carl Walsh ответ, чтобы на самом деле распечатать результат во время компиляции:
#define VALUE (1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+\
21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39+40+\
41+42+43+44+45+46+47+48+49+50+51+52+53+54+55+56+57+58+59+60+\
61+62+63+64+65+66+67+68+69+70+71+72+73+74+75+76+77+78+79+80+\
81+82+83+84+85+86+87+88+89+90+91+92+93+94+95+96+97+98+99+100+\
101+102+103+104+105+106+107+108+109+110+111+112+113+114+115+116+117+118+119+120+\
121+122+123+124+125+126+127+128+129+130+131+132+133+134+135+136+137+138+139+140+\
141+142+143+144+145+146+147+148+149+150+151+152+153+154+155+156+157+158+159+160+\
161+162+163+164+165+166+167+168+169+170+171+172+173+174+175+176+177+178+179+180+\
181+182+183+184+185+186+187+188+189+190+191+192+193+194+195+196+197+198+199+200+\
201+202+203+204+205+206+207+208+209+210+211+212+213+214+215+216+217+218+219+220+\
221+222+223+224+225+226+227+228+229+230+231+232+233+234+235+236+237+238+239+240+\
241+242+243+244+245+246+247+248+249+250+251+252+253+254+255+256+257+258+259+260+\
261+262+263+264+265+266+267+268+269+270+271+272+273+274+275+276+277+278+279+280+\
281+282+283+284+285+286+287+288+289+290+291+292+293+294+295+296+297+298+299+300+\
301+302+303+304+305+306+307+308+309+310+311+312+313+314+315+316+317+318+319+320+\
321+322+323+324+325+326+327+328+329+330+331+332+333+334+335+336+337+338+339+340+\
341+342+343+344+345+346+347+348+349+350+351+352+353+354+355+356+357+358+359+360+\
361+362+363+364+365+366+367+368+369+370+371+372+373+374+375+376+377+378+379+380+\
381+382+383+384+385+386+387+388+389+390+391+392+393+394+395+396+397+398+399+400+\
401+402+403+404+405+406+407+408+409+410+411+412+413+414+415+416+417+418+419+420+\
421+422+423+424+425+426+427+428+429+430+431+432+433+434+435+436+437+438+439+440+\
441+442+443+444+445+446+447+448+449+450+451+452+453+454+455+456+457+458+459+460+\
461+462+463+464+465+466+467+468+469+470+471+472+473+474+475+476+477+478+479+480+\
481+482+483+484+485+486+487+488+489+490+491+492+493+494+495+496+497+498+499+500+\
501+502+503+504+505+506+507+508+509+510+511+512+513+514+515+516+517+518+519+520+\
521+522+523+524+525+526+527+528+529+530+531+532+533+534+535+536+537+538+539+540+\
541+542+543+544+545+546+547+548+549+550+551+552+553+554+555+556+557+558+559+560+\
561+562+563+564+565+566+567+568+569+570+571+572+573+574+575+576+577+578+579+580+\
581+582+583+584+585+586+587+588+589+590+591+592+593+594+595+596+597+598+599+600+\
601+602+603+604+605+606+607+608+609+610+611+612+613+614+615+616+617+618+619+620+\
621+622+623+624+625+626+627+628+629+630+631+632+633+634+635+636+637+638+639+640+\
641+642+643+644+645+646+647+648+649+650+651+652+653+654+655+656+657+658+659+660+\
661+662+663+664+665+666+667+668+669+670+671+672+673+674+675+676+677+678+679+680+\
681+682+683+684+685+686+687+688+689+690+691+692+693+694+695+696+697+698+699+700+\
701+702+703+704+705+706+707+708+709+710+711+712+713+714+715+716+717+718+719+720+\
721+722+723+724+725+726+727+728+729+730+731+732+733+734+735+736+737+738+739+740+\
741+742+743+744+745+746+747+748+749+750+751+752+753+754+755+756+757+758+759+760+\
761+762+763+764+765+766+767+768+769+770+771+772+773+774+775+776+777+778+779+780+\
781+782+783+784+785+786+787+788+789+790+791+792+793+794+795+796+797+798+799+800+\
801+802+803+804+805+806+807+808+809+810+811+812+813+814+815+816+817+818+819+820+\
821+822+823+824+825+826+827+828+829+830+831+832+833+834+835+836+837+838+839+840+\
841+842+843+844+845+846+847+848+849+850+851+852+853+854+855+856+857+858+859+860+\
861+862+863+864+865+866+867+868+869+870+871+872+873+874+875+876+877+878+879+880+\
881+882+883+884+885+886+887+888+889+890+891+892+893+894+895+896+897+898+899+900+\
901+902+903+904+905+906+907+908+909+910+911+912+913+914+915+916+917+918+919+920+\
921+922+923+924+925+926+927+928+929+930+931+932+933+934+935+936+937+938+939+940+\
941+942+943+944+945+946+947+948+949+950+951+952+953+954+955+956+957+958+959+960+\
961+962+963+964+965+966+967+968+969+970+971+972+973+974+975+976+977+978+979+980+\
981+982+983+984+985+986+987+988+989+990+991+992+993+994+995+996+997+998+999+1000)
char tab[VALUE];
int main()
{
tab = 5;
}
gcc выходы:
test.c: In function 'main':
test.c:56:9: error: incompatible types when assigning to type 'char[500500]' fro
m type 'int'
Ответ 10
Вы можете использовать (и в основном злоупотреблять) макросы/шаблоны С++ для metaprogramming.
AFAIK, Java не допускает такого же типа.
Ответ 11
В теории вы можете использовать это:
#include <iostream>
template<int N>
struct Triangle{
static int getVal()
{
return N + Triangle<N-1>::getVal();
}
};
template<>
struct Triangle<1>{
static int getVal()
{
return 1;
}
};
int main(){
std::cout << Triangle<1000>::getVal() << std::endl;
return 0;
}
(на основе кода, опубликованного Xeo). Но GCC дает мне эту ошибку:
triangle.c++:7: error: template instantiation depth exceeds maximum of 500 (use -ftemplate-depth-NN to increase the maximum) instantiating struct Triangle<500>
плюс огромная псевдо-стоп-трасса.
Ответ 12
Используя java, вы можете сделать что-то похожее на ответ С#:
public class Cheat {
public static final int x = (1000 *1001/2);
}
javac -Xprint Cheat.java
public class Cheat {
public Cheat();
public static final int x = 500500;
}
вы можете сделать это в scala с использованием номеров peano, потому что вы можете заставить компилятор выполнять рекурсию, но я не думаю, что вы можете сделать то же самое в С#/java
другое решение, не использующее -Xprint, но еще более изворотливое
public class Cheat {
public static final int x = 5/(1000 *1001/2 - 500500);
}
javac -Xlint:all Cheat.java
Cheat.java:2: warning: [divzero] division by zero
public static final int x = 5/(1000 *1001/2 - 500500);
^
1 warning
без использования каких-либо флагов компилятора. так как вы можете проверить произвольное количество констант (не только 500500), это решение должно быть приемлемым.
public class Cheat {
public static final short max = (Short.MAX_VALUE - 500500) + 1001*1000/2;
public static final short overflow = (Short.MAX_VALUE - 500500 + 1) + 1001*1000/2;
}
Cheat.java:3: error: possible loss of precision
public static final short overflow = (Short.MAX_VALUE - 500500 + 1) + 1001*1000/2;
^
required: short
found: int
1 error
Ответ 13
Хотя это действительно работает с небольшими числами, clang++ возвращает мне ошибку компилятора, если я использую sum_first где N > 400.
#include <iostream>
using namespace std;
template <int N>
struct sum_first
{
static const int value = N + sum_first<N - 1>::value;
};
template <>
struct sum_first<0>
{
static const int value = 0;
};
int main()
{
cout << sum_first<1000>::value << endl;
}
