sharp - ¿Cómo manejar el compilador C#, C++ o Java para calcular 1+2+3+...+1000?
lenguajes de programacion (13)
En una entrevista reciente, me hicieron una pregunta realmente extraña. El entrevistador me preguntó cómo puedo calcular 1 + 2 + 3 + ... + 1000 simplemente usando las características del compilador. Esto significa que no tengo permiso para escribir un programa y ejecutarlo, pero solo debería escribir un programa que pueda conducir al compilador a calcular esta suma mientras compilo e imprimir el resultado cuando la compilación finalice. Como una pista, me dijo que puedo usar genéricos y funciones de preprocesador del compilador. Es posible usar el compilador C ++, C # o Java. ¿¿¿Algunas ideas???
Esta pregunta no está relacionada con calcular la suma sin ningún bucle aquí . Además, debe tenerse en cuenta que la suma DEBERÍA calcularse durante la compilación. Imprimir solo el resultado utilizando las directivas del compilador C ++ no es aceptable.
Al leer más sobre las respuestas publicadas, descubrí que resolver problemas durante la compilación usando plantillas C ++ se llama metaprogramación . Esta es una técnica que fue descubierta accidentalmente por el Dr. Erwin Unruh, durante el proceso de estandarización del lenguaje C ++. Puede leer más sobre este tema en la página wiki de meta-programación . Parece que es posible escribir el programa en Java usando anotaciones java. Puede echar un vistazo a maress''s respuesta maress''s continuación.
Un buen libro sobre meta-programación en C ++ es este . Vale la pena echar un vistazo si está interesado.
Una útil biblioteca de meta-programación de C ++ es MPL de Boost en este enlace .
Solo debería escribir un programa que podría conducir al compilador a calcular esta suma durante la compilación e imprimir el resultado cuando finalice la compilación.
Un truco popular para imprimir un número durante la compilación es intentar acceder a un miembro inexistente de una plantilla instanciada con el número que desea imprimir:
template<int> struct print_n {};
print_n<1000 * 1001 / 2>::foobar go;
El compilador dice:
error: ''foobar'' in ''struct print_n<500500>'' does not name a type
Para obtener un ejemplo más interesante de esta técnica, vea Resolver el problema de las ocho reinas en tiempo de compilación .
Aquí hay una implementación que funciona bajo VC ++ 2010. Tuve que dividir los cálculos en 3 etapas, ya que el compilador se quejó cuando las plantillas se repusieron más de 500 veces.
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;
Cuando compile esto, debería ver esta salida del compilador algo como esto:
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> ]
Aunque esto realmente funciona con números pequeños, clang ++ me devuelve un error de compilación si estoy usando sum_first donde 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;
}
Dado que ni el compilador ni el lenguaje se especificaron en la pregunta de la entrevista, me atrevo a presentar una solución en Haskell usando GHC:
{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS_GHC -ddump-splices #-}
module Main where
main :: IO ()
main = print $(let x = sum [1 :: Int .. 1000] in [| x |])
Compilarlo:
$ 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 ...
Y tenemos un programa de trabajo también.
Ejemplo de C # a error en tiempo de compilación.
class Foo
{
const char Sum = (1000 + 1) * 1000 / 2;
}
Produce el siguiente error de compilación:
Constant value ''500500'' cannot be converted to a ''char''
En java, pensé en usar el proceso de anotación. La herramienta apt escanea el archivo fuente antes de analizar realmente el archivo fuente al comando javac.
Durante la compilación de los archivos fuente, la salida se imprimirá:
@Documented
@Retention(RetentionPolicy.RUNTIME)
@Target({ElementType.TYPE, ElementType.METHOD})
public @interface MyInterface {
int offset() default 0;
int last() default 100;
}
La fábrica del procesador:
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);
}
}
El procesador de anotación real:
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)));
}
}
}
}
Luego creamos un archivo fuente. clase simple que usa la anotación 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());
}
}
El procesador de anotación se compila en un archivo jar, luego la herramienta apt se usa para compilar el archivo fuente como sigue:
apt -cp "D:/Variance project/PracticeProject/dist/practiceproject.jar" -factory practiceproject.annotprocess.MyInterfaceAnnotationProcessorFactory "D:/Variance project/PracticeProject2/src/practiceproject2/Main.java"
El resultado del proyecto:
Called supportedAnnotationTypes...........................
Called getProcessorFor................
Sum: 5000
Sum: 500500
En teoría, puedes usar esto:
#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;
}
(basado en el código que Xeo publicó). Pero GCC me da este error:
triangle.c++:7: error: template instantiation depth exceeds maximum of 500 (use -ftemplate-depth-NN to increase the maximum) instantiating struct Triangle<500>
además de una enorme pseudo-stacktrace.
Extendido de la respuesta de Carl Walsh para realmente imprimir el resultado durante la compilación:
#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;
}
Salidas gcc:
test.c: In function ''main'':
test.c:56:9: error: incompatible types when assigning to type ''char[500500]'' fro
m type ''int''
La vida será mucho más fácil con C ++ 11 que agrega funciones constexpr para el cálculo del tiempo de compilación, aunque solo son compatibles actualmente con gcc 4.6 o posterior.
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;
El estándar solo requiere que el compilador admita una profundidad de recursión de 512, por lo que aún debe evitar la profundidad de recursión lineal. Aquí está el resultado:
$ 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
Por supuesto, puedes usar la fórmula:
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");
Me siento obligado a dar este código C, ya que nadie más lo ha hecho aún:
#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);
}
¡Y todo lo que necesito hacer es verificar el ensamblaje para encontrar mi respuesta!
gcc -S compile_sum.c;
grep "/$[0-9]*, *-4" compile_sum.s
Y veo:
movl $500500, -4(%rbp)
Puede usar (y sobre todo abusar) macros / plantillas C ++ para hacer metaprogramación . AFAIK, Java no permite el mismo tipo de cosas.
Usando Java puedes hacer algo similar a la respuesta de C #:
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;
}
Puedes hacer esto en scala usando números de peano porque puedes obligar al compilador a hacer la recursión, pero no creo que puedas hacer lo mismo en c # / java
otra solución que no usa -Xprint pero aún más dudosa
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
sin usar ningún indicador de compilación. dado que puede verificar una cantidad arbitraria de constantes (no solo 500500), esta solución debería ser aceptable.
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
¡Actualizado ahora con una profundidad de recursión mejorada! Funciona en MSVC10 y GCC sin mayor profundidad. :)
Simple recursión en tiempo de compilación + adición:
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;
};
Código de prueba:
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();
}
Salida para GCC:
error: declaración de ''struct sum_from <1u> :: a <1000u> :: igual <500500u>''
Salida para MSVC10:
error C2514: ''sum_from<Start>::to<Goal>::equals<Result>'' : class has no constructors
with
[
Start=1,
Goal=1000,
Result=500500
]